Trampoline TS

A type-safe way to emulate tail-call optimization with trampolines

Install

npm i trampoline-ts
# or
yarn add trampoline-ts

TypeScript Compatibility

Requires a TypeScript version >= 3.0

Usage

import { trampoline, ThunkOrValue } from 'trampoline-ts';

const factorial = trampoline((n: number, acc: number = 1): ThunkOrValue<number> => {
  return n
    // Note: calling factorial.cont instead of factorial directly
    ? factorial.cont(n - 1, acc * n)
    : acc;
});

factorial(32768); // No stack overflow

API

trampoline<F extends ((...args: any[]) => ThunkOrValue<any>)>(fn: F): Trampoline<F>

Takes a Tail Recursive Form function that returns a ThunkOrValue<T> and converts it to a tail-call optimized function. The returned function Trampoline<F> will have the exact same type signature as the passed function except for one change, the return type will not contain ThunkOrValue<T>, it will just be T.

It's important that fn wraps the return type in ThunkOrValue. If this is omitted, TypeScript will not be able to infer the type of the returned function and will default to any.

Also note that to continue function recursion Trampoline<F>.cont() should be called, and not the function directly. .cont() has the same type signature as the passed function, so there's no way to call it incorrectly.

Trampoline<F extends ((...args: any[]) => ThunkOrValue<any>>

A function that represents a tail-call optimized function.

Trampoline<F>.cont(...args: ArgumentTypes<F>): Thunk<ReturnType<F>>

Function used to safely continue recursion. It captures F's argument and return types and thus has the same type signature.