Trampolining in Typescript

trampoline.ts

// stub for typescript
declare function BigInt(n: number): number

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]))
  }
}

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)
  }
}

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 new Done(a)
}

function more<A>(a: () => Trampoline<A>): More<A> {
  return new More(a)
}

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
      }
    }
  }
}

// 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(interpret(fib_TRAMPOLINED)(10000))

How it will work if program is

const fib = (desiredCount: number): number => {
  const itar = (a: number, b: number, count: number): number => {
    if (count === desiredCount) {
      return a + b
    } else {
      return a+itar(b, a + b, count + 1)
    }
  }
  return itar(BigInt(0), BigInt(1), 0) // recursive call
}

This is a more complex use case where we would need to implement more advanced features inside of trampoline. —

Trampoline

abstract class Trampoline<A> {
  abstract map<B>(ab: (a: A) => B): Trampoline<B>
  abstract flatMap<B>(ab: (a: A) => Trampoline<B>): Trampoline<B>


  // The new ZIP operator can help us with combining two Trampolines.
  zip<B>(tb: Trampoline<B>): Trampoline<[A, B]> {
    const ta = this
    return ta.flatMap(a => tb.map(b => [a, b] as [A, B]))
  }
}

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)
  }
}

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))
  }
}

Very useful code for me. thanks a lot!!