module Trampoline where {-| A [trampoline](http://en.wikipedia.org/wiki/Tail-recursive_function#Through_trampolining) 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 to 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 @docs trampoline, Trampoline -} import Native.Trampoline {-| 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 : [a] -> Int length list = length' 0 list length' : Int -> [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 : [a] -> Int length list = trampoline (length' 0 list) length' : Int -> [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! -} type Trampoline a = Done a | Continue (() -> Trampoline a) {-| Evaluate a trampolined value in constant space. -} trampoline : Trampoline a -> a trampoline = Native.Trampoline.trampoline