trampoline typescript

tramp.ts

/**
 * Transforms a function that returns either a direct value or a thunk (a
 * no-argument function that returns a value) into a function that only returns
 * a direct value. It does this by repeatedly evaluating the function if it
 * returns a thunk, until a direct value is obtained.
 *
 * @template T The type of the value to be returned by the trampoline function.
 * @template A The type tuple representing the argument types accepted by the
 * function f.
 * @param f A function that takes arguments of type A and returns either a
 * value of type T or a thunk that returns T.
 * @returns A function that takes the same arguments but guarantees to return a
 * direct value of type T.
 *
 * Converting a recursive function to use trampoline:
 * 1. Create an auxiliary function that takes the same parameters as the
 *    original function, plus an accumulator parameter.
 * 2. Modify the base case to return the accumulator instead of a fixed value.
 * 3. Replace the recursive call with a thunk (a function that returns the next
 *    recursive step).
 * 4. Use the tramp function to create the final trampolined version.
 *
 * Reasoning:
 * - The accumulator is necessary because we can't directly use the return
 *   value of the recursive call. Instead, we pass the intermediate results
 *   through the accumulator.
 * - This allows us to convert the recursive calls into a series of thunks,
 *   which the trampoline function can then execute iteratively, avoiding
 *   stack overflow for deep recursions.
 * 
 * Example conversion:
 * ```typescript
 * // Original recursive function
 * function factorial(n: bigint): bigint {
 *   if (n <= 1) return 1n;
 *   return n * factorial(n - 1n);
 * }
 * 
 * // Trampolined version:
 * function factorialAux(n: bigint, acc = 1n): bigint | Thunk<bigint> {
 *   if (n <= 1) return acc;
 *   return () => factorialAux(n - 1n, n * acc);
 * }
 * const trampolinedFactorial = tramp(factorialAux);
 * ```
 */
export function tramp<T, A extends readonly any[]>(f: (...args: A) => (T | Thunk<T>)): (...args: A) => T {
    return (...args: A) => {
        let result = f(...args);
        while (is_thunk(result)) {
            result = result();
        }
        return result;
    };
}

export type Thunk<T> = () => T;

export function is_thunk<T>(v: T | Thunk<T>): v is Thunk<T> {
    return typeof v === "function" && v.length === 0;
}