This text problematizes recursion in Elm and explores how to deal with recursive data without free access to recursion in functions.
NOTE: Sorry in advanced if this text isn't very well paced or the concepts not very well explained. I've done my best, but i find writing texts like this to be hard. If you have trouble understanding parts please contact me if you want! @emmabastas in the Elm Slack.
Being able to do recursion (or loops) is considered essential for any worthy programming language. But do we really want it? In Elm, infinite recursion is one of the few ways in which a program can crash. You can also use recursion to do some pretty questionable stuff:
{-| When you _just_ know that a `Maybe` is a `Just` but that pesky compiler complains
-}
just : Maybe a -> a
just maybe =
case maybe of
Just x ->
x
Nothing ->
-- Will crash the program
just NothingWouldn't it be nice if we could guarantee that every piece of Elm code always terminates? I (or a package I depend on) would no longer be able to accidentally crash, and it wouldn't be possible to circumvent the compiler like in the above example.
Let's explore what happens if we restrict recursion to just whitelisted packages.
One can think of a List as a recursive type that looks like this internally:
type List a
= Nil
| Cons a (List a)And list syntax is really just syntactic sugar for Nil and Cons:
[] == Nil
[ 1, 2, 3 ] == Cons 1 (Cons 2 (Cons 3 Nil))A function like foldr can be implemented as a recursive function:
foldr : (a -> b -> b) -> b -> List a -> b
foldr func acc list =
case list of
Nil ->
acc
Cons x xs ->
func x (foldr func acc xs)With foldr we can do about everything we'd want to without having to use recursion ourselves.
map : (a -> b) -> List a -> List b
map func list =
foldr (\x xs -> Cons (func x) xs) Nil list
append : List a -> List a -> List a
append l1 l2 =
foldr Cons l2 l1
reverse : List a -> List a
reverse =
foldr (\x reversed -> append reversed (Cons x Nil)) NilIf foldr always terminates, so will map, append, reverse and any other function built with foldr.
So even though lists are recursive by nature, we rarely need recursion to deal with them. We can define one single List type and one single foldr function and with these two components we can model and operate on any list-like data we want to. No recursion on our part needed. That's pretty nifty!
So forbidding recursion is not really a problem when it comes to lists.
Like we did with lists, we could try to define some Tree type and some sort of fold function which encompasses everything we'd want to do with tree-like data. This is however not feasible because while there's really only one way one might want to represent and traverse list-like data, tree-like data on the other hand is very diverse.
There's binary, m-ary, multi-way and an infinite(?) variation of trees in-between. We need to take another approach...
This is a possible solution I came up with.
We define an opaque type called Recurse in the module Safe.Recursion. This module is whitelisted so it can use recursion all it wants!
module Safe.Recursion exposing (Recurse)
type Recurse a
= Recurse aSay that we want to make a type representing a mathematical expression like 3 * (5 + 7). Normally we'd do something like this:
type Expr
= Num Int
| Add Expr Expr
| Mul Expr ExprBut with the Recurse type we instead do this:
type Expr
= Num Int
| Add (Recurse Expr) (Recurse Expr) -- `Expr` is replaced with `Recurse Expr`
| Mul (Recurse Expr) (Recurse Expr)The idea is that recursion is dangerous, so we shouldn't deal with it ourselves. Any recursion is wrapped in the Recurse type which is opaque. So the only way to deal with recursive data is via utility functions in Safe.Recursion.
If we want to build an Expr value we'd use Safe.Recursion.build:
----------- Safe.Recursion -----------
build : ((a -> Recurse a) -> a) -> a
build f =
f Recurse
----------- MyModule -----------------
-- 3 * (5 + 7)
myExpression : Expr
myExpression =
Safe.Recursion.build
(\recurse ->
Mul
(recurse (Num 3))
(recurse
(Add
(recurse (Num 5))
(recurse (Num 7))
)
)
)If we want to traverse the data and transform it we'd use Safe.Recursion.traverse:
----------- Safe.Recursion -----------
traverse : ((Recurse a -> b) -> a -> b) -> a -> b
traverse f x =
f (\(Recurse y) -> traverse f y) x
---------- MyModule ------------------
-- we can sum the expression. sum myExpresion == 36
sum : Expr -> Int
sum =
Safe.Recursion.traverse
(\recurse expr ->
case expr of
Num n ->
n
Add expr1 expr2 ->
recurse expr1 + recurse expr2
Mul expr1 expr2 ->
recurse expr1 * recurse expr2
)
-- we can even change the structure of our data.
-- mirror `3 * (5 + 7)` -> `(7 + 5) * 3`
mirror : Expr -> Expr
mirror =
let
makeNode =
\nodeConstructor expr1 expr2 ->
Safe.Recursion.build
(\recurse ->
nodeConstructor (recurse expr1) (recurse expr2)
)
in
Safe.Recursion.traverse
(\recurse expr ->
case expr of
Num n ->
Num n
Add expr1 expr2 ->
makeNode Add (recurse expr2) (recurse expr1)
Mul expr1 expr2 ->
makeNode Mul (recurse expr2) (recurse expr1)
)That's a lot of code that might be hard to make sense of. The general idea anyways is:
- Recursive types are defined with the
Recursetype. - Recursive types can only be constructed within the
buildfunction. There's no way to have a function likewrap : a -> Recurse aoutside ofbuild. - Recursive types can only be traversed within the
traversefunction. There's no way to have a function likeunwrap : Recurse a -> aoutside oftraverse. - The only data that can be recursed into are the current nodes children, meaning that
traversealways terminates!
Maybe there are ways to break the guarantee and get infinite recursion with build and/or traverse? I'd be glad if you'd want to try and figure out if it's possible. I tried for myself but didn't come up with anything.
I think that if you can achieve any of the following two:
- Define a function
wrap : a -> Recurse aoutside ofbuild. - Define a function
unwrap : Recurse a -> aoutside oftraverse.
Then infinite recursion is possible, otherwise it's not.
Custom types in Elm can represent trees, but not graphs. We sort of need to emulate graphs with trees. I suspect that this is harder to accomplish than to just *sprinkle* in Recurse types here and there, and then use traverse and build. Graphs can contain cycles, and we need to guarantee that traversing a graph deals with that. Maybe we need another module with some clever primitives for dealing with graph-like data.
While i think that Recurse, build and traverse are very nifty (though using build is a bit ugly imo) and relatively easy to use, I haven't tried to use it "in the wild". What would decoding and encoding recursive json look like for instance?
I think it's pretty cool that Recurse, build and traverse are so simple yet powerful. You can define any arbitrary custom type, throw some Recurse types into the mix and then you can perform almost any sane operation one might want with build and traverse, and it's guaranteed to always terminate!! And this is all done within the Elm type system, no type classes, higher kinded types and what have you are needed!