Trampoline

A trampoline makes it possible to recursively call a function without growing the stack.

Popular JavaScript implementations do not perform any tail-call elimination, so recursive functions can cause a stack overflow if they go too deep. Trampolines permit unbounded recursion despite limitations in JavaScript.

This strategy may create many intermediate closures, which is very expensive in JavaScript, so use this library only when it is essential that you recurse deeply.

Trampolines

trampoline : Trampoline a -> a

Evaluate a trampolined value in constant space.

type Trampoline a

= Done a

| Continue (() -> Trampoline a)

A way to build computations that may be deeply recursive. We will take an example of a tail-recursive function and rewrite it in a way that lets us use a trampoline:

length : List a -> Int
length list = length' 0 list


length' : Int -> List a -> Int
length' accum list =
    case list of
      []     -> accum
      hd::tl -> length' (accum+1) tl

This finds the length of a list, but if the list is too long, it may cause a stack overflow. We can rewrite it as follows:

length : List a -> Int
length list = trampoline (length' 0 list)


length' : Int -> List a -> Trampoline Int
length' accum list =
    case list of
      []     -> Done accum
      hd::tl -> Continue (\() -> length' (accum+1) tl)

Now it uses a trampoline and can recurse without growing the stack!

elm-lang/core/2.0.1

Trampoline

Trampolines

Modules