Skip to content

Instantly share code, notes, and snippets.

@tusharmath

tusharmath/trampoline.ts

Last active March 31, 2023 01:05
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save tusharmath/f1eaa6e0bdb3cc2c37835497a85c0b60 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save tusharmath/f1eaa6e0bdb3cc2c37835497a85c0b60 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. tusharmath revised this gist May 9, 2019. 1 changed file with 42 additions and 18 deletions.
    60 changes: 42 additions & 18 deletions trampoline.ts
    View file
    Original file line number Diff line number Diff line change
    @@ -1,34 +1,58 @@
    // stub for typescript
    declare function BigInt(n: number): number

    type Done<A> = {
    type: 'DONE'
    value: A
    abstract class Trampoline<A> {
    abstract map<B>(ab: (a: A) => B): Trampoline<B>
    abstract flatMap<B>(ab: (a: A) => Trampoline<B>): Trampoline<B>

    zip<B>(tb: Trampoline<B>): Trampoline<[A, B]> {
    const ta = this
    return ta.flatMap(a => tb.map(b => [a, b] as [A, B]))
    }
    }

    type More<A> = {
    type: 'MORE'
    fn: () => Trampoline<A>
    class Done<A> extends Trampoline<A> {
    constructor(readonly a: A) {
    super()
    }
    map<B>(ab: (a: A) => B): Trampoline<B> {
    return new Done(ab(this.a))
    }
    flatMap<B>(ab: (a: A) => Trampoline<B>): Trampoline<B> {
    return ab(this.a)
    }
    }

    type Trampoline<A> = Done<A> | More<A>
    class More<A> extends Trampoline<A> {
    constructor(readonly fn: () => Trampoline<A>) {
    super()
    }

    map<B>(ab: (a: A) => B): Trampoline<B> {
    return new More(() => this.fn().map(ab))
    }
    flatMap<B>(ab: (a: A) => Trampoline<B>): Trampoline<B> {
    return new More(() => this.fn().flatMap(ab))
    }
    }

    function done<A>(a: A): Done<A> {
    return {type: 'DONE', value: a}
    return new Done(a)
    }

    function more<A>(a: () => Trampoline<A>): More<A> {
    return {type: 'MORE', fn: a}
    return new More(a)
    }

    const interpret = <A>(t: Trampoline<A>): A => {
    let result: Trampoline<any> = t
    while (true) {
    switch (result.type) {
    case 'DONE':
    return result.value
    case 'MORE':
    const interpret = <ARGS extends any[], R>(fn: (...t: ARGS) => Trampoline<R>) => {
    return (...t: ARGS): R => {
    let result: Trampoline<any> = fn(...t)
    while (true) {
    if (result instanceof More) {
    result = result.fn()
    } else if (result instanceof Done) {
    return result.a
    }
    }
    }
    }
    @@ -58,7 +82,7 @@ const fib_TRAMPOLINED = (desiredCount: number): Trampoline<number> => {
    }

    // RangeError: Maximum call stack size exceeded
    console.log(fib(10000))
    // console.log(fib(10000))

    // Works yay!
    console.log(interpret(fib_TRAMPOLINED)(10000))
    console.log(interpret(fib_TRAMPOLINED)(10000))
  2. tusharmath revised this gist May 9, 2019. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion trampoline.ts
    View file
    Original file line number Diff line number Diff line change
    @@ -61,4 +61,4 @@ const fib_TRAMPOLINED = (desiredCount: number): Trampoline<number> => {
    console.log(fib(10000))

    // Works yay!
    console.log(fib_TRAMPOLINED(10000))
    console.log(interpret(fib_TRAMPOLINED)(10000))
  3. tusharmath created this gist Nov 25, 2018.
    64 changes: 64 additions & 0 deletions trampoline.ts
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,64 @@
    // stub for typescript
    declare function BigInt(n: number): number

    type Done<A> = {
    type: 'DONE'
    value: A
    }

    type More<A> = {
    type: 'MORE'
    fn: () => Trampoline<A>
    }

    type Trampoline<A> = Done<A> | More<A>

    function done<A>(a: A): Done<A> {
    return {type: 'DONE', value: a}
    }

    function more<A>(a: () => Trampoline<A>): More<A> {
    return {type: 'MORE', fn: a}
    }

    const interpret = <A>(t: Trampoline<A>): A => {
    let result: Trampoline<any> = t
    while (true) {
    switch (result.type) {
    case 'DONE':
    return result.value
    case 'MORE':
    result = result.fn()
    }
    }
    }

    // Simple implementation that throws a stack overflow exception
    const fib = (desiredCount: number): number => {
    const itar = (a: number, b: number, count: number): number => {
    if (count === desiredCount) {
    return a + b
    } else {
    return itar(b, a + b, count + 1)
    }
    }
    return itar(BigInt(0), BigInt(1), 0) // recursive call
    }

    // Works without any issues
    const fib_TRAMPOLINED = (desiredCount: number): Trampoline<number> => {
    const itar = (a: number, b: number, count: number): Trampoline<number> => {
    if (count === desiredCount) {
    return done(a + b)
    } else {
    return more(() => itar(b, a + b, count + 1))
    }
    }
    return itar(BigInt(0), BigInt(1), 0) // recursive call
    }

    // RangeError: Maximum call stack size exceeded
    console.log(fib(10000))

    // Works yay!
    console.log(fib_TRAMPOLINED(10000))