This module provides an abstraction over general recursion that allows the recursive computation to be executed without risk of blowing the stack.
If you are unfamiliar with why we need to be careful about unsafe recursion in Elm, this article describes the Tail-Call Elimination very well.
It is not terribly difficult to rewrite simple recursions to be safe by taking advantage of the Tail Call Optimization. However, the moment you need to recurse on two or more elements in a data structure it becomes quite hairy to write safely and the resulting code loses much of the beauty of recursion.
This module presents ways to create and execute the Rec monad, which is sufficiently powerful to represent non-simple recursion safely and will allow
you to preserve the recursive elegance that makes functional programming beautiful.
RecThe base case of a recursion. The value is injected directly into the Rec type.
Recurse on a value.
When the recursion is complete the Rec will contain a value of type t.
Recurse on a value and then take another action on the result.
If you find yourself writing code that looks like recurse x |> andThen ... or recurse x |> map ... you should
consider using recurseThen instead as it will be much more efficient.
RecApply a function to the recursive type of a Rec computation
Apply a function to the result of a Rec computation that can specify more recursion.
Check out Recursion.Traverse
and Recursion.Fold
for helpers that work with containers of recursive types.
RecRun a recursion given a function to run one layer and an initial value.
Like runRecursion but carries an additional state variable the recursion proceeds
Note that state is not accumulated across siblings, but rather passed from parent to child.
Imagine we have a generic binary tree type that we want to write a map function for:
type Tree a
= Leaf a
| Node (Tree a) (Tree a)The standard recursive map algorithm is straightforward:
mapTree : (a -> b) -> Tree a -> Tree b
mapTree f tree =
case tree of
Leaf a ->
Leaf (f a)
Node l r ->
Node (mapTree f l) (mapTree f r)⚠️⚠️⚠️ This is unsafe! ⚠️⚠️⚠️
Since the recursive calls to mapTree are not located in tail call position the Tail Call Optimization will not fire.
We are exposing ourselves to a crash if the tree is deep enough that we would have a stack overflow while executing it!
mapTree : (a -> b) -> Tree a -> Tree b
mapTree f initTree =
runRecursion
(\tree ->
case tree of
Leaf a ->
base (Leaf (f a))
Node l r ->
recurseThen l
(\newL ->
recurseThen r
(\newR ->
baes <| Node newL newR
)
)
)
initTree
An opaque type representing a recursive computation.
ris the recursive type.tis the target type that we are converting to.ais a type for intermediate parts of the computation.I think it is helpful to think of
Reclike thePromisetype in javascript. Simliar to aPromise, the result in aRecvalue might not be available yet because it needs to recursively evaluated in a separate step. So instead of directly manipulating the value in aRec, we instead can specify actions to be done with the value when it is available usingmapandandThen.