git.iko.soy/elk
on 577fc17 help sign in
elk/libraries/Trampoline.elm
49 lines 1.7 kB history raw
1module Trampoline where
2{-| A [trampoline](http://en.wikipedia.org/wiki/Tail-recursive_function#Through_trampolining)
3makes it possible to recursively call a function without growing the stack.
5Popular JavaScript implementations do not perform any tail-call elimination, so
6recursive functions can cause a stack overflow if they go to deep. Trampolines
7permit unbounded recursion despite limitations in JavaScript.
9This strategy may create many intermediate closures, which is very expensive in
10JavaScript, so use this library only when it is essential that you recurse deeply.
12# Trampolines
13@docs trampoline, Trampoline
14-}
16import Native.Trampoline
18{-| A way to build computations that may be deeply recursive. We will take an
19example of a tail-recursive function and rewrite it in a way that lets us use
20a trampoline:
22 length : [a] -> Int
23 length list = length' 0 list
25 length' : Int -> [a] -> Int
26 length' accum list =
27 case list of
28 [] -> accum
29 hd::tl -> length' (accum+1) tl
31This finds the length of a list, but if the list is too long, it may cause a
32stack overflow. We can rewrite it as follows:
34 length : [a] -> Int
35 length list = trampoline (length' 0 list)
37 length' : Int -> [a] -> Trampoline Int
38 length' accum list =
39 case list of
40 [] -> Done accum
41 hd::tl -> Continue (\() -> length' (accum+1) tl)
43Now it uses a trampoline and can recurse without growing the stack!
44-}
45data Trampoline a = Done a | Continue (() -> Trampoline a)
47{-| Evaluate a trampolined value in constant space. -}
48trampoline : Trampoline a -> a
49trampoline = Native.Trampoline.trampoline