Recently, I’ve been translating some algorithms from imperative (Javascript/Python) languages to Elm. In this process, the conversion of loops to functional code always requires a lot of attention, mostly because loops imply mutation. Here are some strategies for rewriting common loops patterns in Elm using folds, unfolds, and paramorphisms.

# Folds

Folds are very general functions that capture the idea of “collapsing a structure into a value”. The most common folds are left (`List.foldl`

) and right (`List.foldr`

) folds for lists. Most list functions can be expressed as folds, notably List.filter and List.map.

## Collapsing a structure into one value

```
var result = 0;
for ( var i = 0; i <= 10; i++) {
result += i;
}
```

In Elm, this sort of function is typically written recursively. The recursive definition can then be generalized into `List.sum`

, which can be written as a fold:

```
sumToTen default n =
if n <= 10 then
sumToTen (n + default ) ( n + 1)
else
n + default
sum numbers =
case numbers of
[] ->
-- base case, note that 0 is the identity under adition
-- which means that `x + 0 = 0 + x = x` for all x.
0
n::ns ->
-- recursive case
n + sum ns
sum = List.foldl (+) 0
sumToTenImproved = sum [0..10]
```

Translating to elm is basically the above snippet: write crude code, generalize, generalize further, and profit.

## Loops with multiple variables

```
var list = [ 3, 42, 73, 2 ];
var min = list[0], max = list[0];
for (var i = 0; i < list.length; i++) {
min = Math.min(min, list[i]);
max = Math.max(max, list[i]);
}
```

Just like above, the body only uses the current element and the result so far: an excellent use case for a fold.

```
folder elem ( min, max ) =
( Basics.min min elem
, Basics.max max elem
)
minmax : List comparable -> Maybe ( comparable, comparable )
minmax list =
case list of
[] ->
Nothing
x::xs ->
Just (List.foldl folder (x, x) xs)
```

Multiple mutable variables are stored in a tuple. The compiler forces handling the case of an empty list.

# Unfold

Unfolds are the categorical dual of folds. This means that they do the opposite of a fold: instead of folding many values into one, unfold unfolds one value into many.

```
foldr : ( a -> b -> b) -> b -> List a -> b
foldr function default list = ...
unfoldr : (b -> Maybe (a, b)) -> b -> List a
unfoldr function default = ...
-- a variant of unfold that
-- * separates the predicate from the update
-- * only keeps the most recent result
until : (a -> Bool) -> (a -> a) -> a -> a
until predicate function default = ...
```

`unfoldr`

can be found in the elm-community/list-extra package

Unfold seems perfect for rewriting a while-loop: it exectutes some code repeatedly until a condition is True. the loop body becomes a function that returns `Nothing`

when it’s done and `Just (producedValue, nextState)`

when it continues.

## Looping until a structure is empty

This is a simple function with a while-loop. It doesn’t really serve a purpose, but has three important characteristics that I want to recreate in elm:

- The body can modify the object being looped over (the range is not known in advance)
- The mutated ‘remaining’ list is used in the body
- The updating of the result is non-commutative (because
`"a" ++ "b" /= "b" ++ "a"`

)

```
def loopUntilEmpty(myList):
result = ""
while myList != []:
item = myList.pop()
if len(item) < 16:
# prepend the new items
myList = [ item + item ] + myList
# use mutated version of myList
result += "-" + str(len(myList)) + "-"
return result
print(loopUntilEmpty(["-A-", "-B-", "-C-", "--D-"]))
```

This snippet prints

`-4--4--4--4--4--4--4--4--3--3--3-`

The body function needs to take as arguments the current element, any remaining elements, and the result so far. It can **break** by returning `Nothing`

and **continue** by returning the input values for remainder and accum.

```
body : String -> List String -> String -> Maybe (List String, String)
body current remainder accum =
if String.length current < 16 then
let
newRemainder =
remainder ++ [ current ++ current ]
newAccum =
String.join "-"
[ accum
, toString (List.length newRemainder)
, ""
]
in
Just ( newRemainder, newAccum )
else
Just ( remainder, accum )
```

With some type tetris, the helper for `unfoldr`

is reasonably straightforward.

```
untilEmpty :
(a -> List a -> b -> Maybe ( List a, b ))
-> b
-> List a
-> b
untilEmpty f default list =
let
prependAccum ( remainder, accum ) =
( accum, ( remainder, accum ) )
--helper : ( List a, b ) -> Maybe ( b, ( List a, b ) )
helper ( list, result ) =
case list of
[] ->
Nothing
x :: xs ->
f x xs result
|> Maybe.map prependAccum
in
List.unfoldr helper ( list, default )
|> List.reverse
|> List.head
|> Maybe.withDefault default
myList =
List.reverse [ "-A-", "-B-", "-C-", "--D-" ]
loopUntilEmpty myList =
untilEmpty body "" myList
```

This solution is quite flexible and compact, but has some rough edges. All the intermediate results are stored, which wastes memory, and to acutally get the result, the final element of a list is needed, which is an expensive operation in Elm.

Also note that the input list is reversed. The reason is that in imperative languages, popping happens at the back of a list, while pattern matching in Elm happens at the front. Actually, differences in data structures (what is the default behavior, what is efficient) are something to look out for in general when rewriting in another language.

# Paramorphisms

A bit of category theory to motivate the next section.

Folds and Unfolds are called Catamorphisms and Anamorphisms in category theory. There are quite a few more -morphisms, with varying levels of usefullness. One of them is especially useful for the problem at hand: the Paramorphism.

Compared to a fold, the paramorphism takes an extra list argument in the per-element function.

```
foldr : (a -> b -> b) -> b -> List a -> b
parar : (a -> List a -> b -> b) -> b -> List a -> b
```

This extra list element is the tail of the list. Where fold only gives the first element `x`

of the list as an argument to func, para also gives the tail `xs`

of the list.

```
-- foldr
x::xs ->
func x (foldr func acc xs)
-- parar
x::xs ->
func x xs (parar func acc xs)
```

Here are the implementations of `paral`

and `parar`

, along with the implementations of `foldl`

and `foldr`

for reference.

```
foldr : (a -> b -> b) -> b -> List a -> b
foldr func acc list =
case list of
[] ->
acc
x::xs ->
func x (foldr func acc xs)
{-| Paramorphism that moves from right to the left.
The `List a` argument in the per-element function is
a list of items that have already been visited.
-}
parar : (a -> List a -> b -> b) -> b -> List a -> b
parar func acc list =
case list of
[] ->
acc
x :: xs ->
func x xs (parar func acc xs)
foldl : (a -> b -> b) -> b -> List a -> b
foldl func acc list =
case list of
[] ->
acc
x :: xs ->
foldl func (func x acc) xs
{-| Paramorphism that moves from left to the right.
The `List a` argument in the per-element function is
a list of items that have not yet been visited.
-}
paral : (a -> List a -> b -> b) -> b -> List a -> b
paral func acc list =
case list of
[] ->
acc
x :: xs ->
paral func (func x xs acc) xs
```

*paramorphisms are not yet available in any elm library*

## while-loops with para

A paramorphism only keeps the most recent result, so the problems that the `unfoldr`

solution has are solved.

To use a paramorphism, we need to make these types match.

```
paral: a -> List a -> b -> b
body : String -> List String -> String -> Maybe (List String, String)
```

Unification of `b = String = Maybe (List String, String)`

is impossible, but the `Maybe (..)`

return type is needed to mutate the `remaining`

list and to be able to **break** from the body. The best fix I see is to make a custom `para`

function

```
-- 'paralMut' for "paramorphism that mutates".
-- Better name suggestions are welcome
paralMut
: (a -> List a -> b -> Maybe ( List a, b ))
-> b
-> List a
-> b
paralMut f base list =
case list of
[] ->
base
x :: xs ->
case f x xs base of
Nothing ->
base
Just ( newList, newBase ) ->
paralMut f newBase newList
```

The following now produces the correct result

```
result =
paralMut body "" myList
```

# Conclusion

With some thinking, loops can be concisely expressed as recursive functions in Elm. The recursion helpers (also refered to as recursion schemes) are what takes some time and experimentation to fully understand. Depending on my future experiments and community interest, I may make a recursion helper package.

In this article, I’ve worked under the assumption that a more-or-less literal translation of imperative to Elm code is what you want. Often it makes sense to rethink the problem, i.e. to completely start from scratch with only a specification.

When writing code that has to give the same output as some existing piece of code, tests are very important (and relatively simple to create). The excellent elm-test package is very helpful in my experience.

Lastly, extracting and using common patterns is - I hope I’ve showed this - extremely useful. It makes expressing a problem so much easier.

### after publication

**Aug 26, 2016**made parallels between folds and paramorphisms more explicit, thanks szabba for the suggestion**Aug 26, 2016**eruonna posted a solution to the above problem using hylomorphisms, thanks!