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