Skip to content

Instantly share code, notes, and snippets.

@emmabastas
Last active August 16, 2020 17:53
Show Gist options
  • Save emmabastas/563a1f04c3b58f85b156e5b8d324bdfe to your computer and use it in GitHub Desktop.
Save emmabastas/563a1f04c3b58f85b156e5b8d324bdfe to your computer and use it in GitHub Desktop.
Thoughts about safe recursion in Elm

Safe recursion in Elm

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.

The troubles with recursion

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 Nothing

Wouldn'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.

Lists

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)) Nil

If 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.

Trees

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...

Solution - Managed recursion

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 a

Say 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 Expr

But 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 Recurse type.
  • Recursive types can only be constructed within the build function. There's no way to have a function like wrap : a -> Recurse a outside of build.
  • Recursive types can only be traversed within the traverse function. There's no way to have a function like unwrap : Recurse a -> a outside of traverse.
  • The only data that can be recursed into are the current nodes children, meaning that traverse always terminates!

More to explore

Breaking the guarantee

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:

  1. Define a function wrap : a -> Recurse a outside of build.
  2. Define a function unwrap : Recurse a -> a outside of traverse.

Then infinite recursion is possible, otherwise it's not.

Graphs

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.

Use in practice

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?

Final remarks

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!

module MyModule exposing (Expr(..), mirror, myExpression, sum)
import Safe.Recursion exposing (Recurse)
type Expr
= Num Int
| Add (Recurse Expr) (Recurse Expr)
| Mul (Recurse Expr) (Recurse Expr)
myExpression : Expr
myExpression =
Safe.Recursion.build
(\recurse ->
Mul
(recurse (Num 3))
(recurse
(Add
(recurse (Num 5))
(recurse (Num 7))
)
)
)
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
)
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)
)
module Safe.Recursion exposing (Recurse, build, traverse)
type Recurse a
= Recurse a
build : ((a -> Recurse a) -> a) -> a
build f =
f Recurse
traverse : ((Recurse a -> b) -> a -> b) -> a -> b
traverse f x =
f (\(Recurse y) -> traverse f y) x
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment