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 "" myListThis 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 -> bThis 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) xsparamorphisms 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 newListThe following now produces the correct result
result =
paralMut body "" myListConclusion
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!