This is a pretty entry level post on functional programming. It concerns the folding patterns in functional programming. I'll be using Elm as an example language, but the ideas are broadly similar in other functional languages. So I'm talking about the fold functions List.foldl and List.foldr. I'll talk about a strict/eager language, though one of the interesting things about folds is that in strict languages the foldl is the 'good' one, whilst in lazy languages the foldr function is the 'good' one. I'm going to try to explain why the foldl is the good one in strict languages, I'll leave why 'foldr' is the good one for lazy languages for another day.
What are the folds #
There are many descriptions of this available with a simple search. However, the idea is to repeatedly apply a function to each element in a list, and the result of the previous application of the function. I find it pretty intuitive to think of 'building' up some kind of data structure. For example, perhaps re-implementing Dict.fromList, that is, building a dictionary from a list of key-value pairs. So first of all the type of both foldl and foldr:
1List.foldl : (a -> b -> b) -> b -> List a -> b
2List.foldr : (a -> b -> b) -> b -> List a -> b
The first argument is our function to be repeatedly applied, the second argument is an initial starting value, and the third argument is the list of items to repeatedly apply the function to. The type of the function we wish to create:
1fromList : List (key, value) -> Dict key value
Whilst I'm a massive fan of polymorphism, sometimes it is easier to reason about functions by just making the types more concreate, so lets consider making this function strictly for a dictionary which maps strings to integers, and hence we start with a list string-int pairs.
1fromList : List (String, Int) -> Dict String Int
So this means that our two fold functions have the instantiated types:
1List.foldl : ((String, Int) -> Dict String Int -> Dict String Int) -> Dict String Int -> List (String, Int) -> Dict String Int
2List.foldr : ((String, Int) -> Dict String Int -> Dict String Int) -> Dict String Int -> List (String, Int) -> Dict String Int
So let's fill in the details:
1fromList : List (String, Int) -> Dict String Int
2fromList keyValues =
3 let
4 insertPair : (String, Int) -> Dict String Int -> Dict String Int
5 insertPair (key, value) dict =
6 Dict.insert key value dict
7 in
8 List.foldl insertPair Dict.empty keyValues
The same thing works for List.foldr. To see how this works, imagine calling this function with a list of exactly one pair, and then a list of exactly two pairs.
The difference between foldl and foldr #
What happens if you use our Dict.fromList to create a dictionary from a list of key-value pairs in which we have a contractitory set of pairs. for example: [ ("a", 1), ("a", 2 ) ]. Well, obviously we'll only have one "a" key in the dictionary, but what will it be mapped to? If you use foldl to write fromList then:
1d = fromList [ ("a", 1), ("a", 2) ]
2Dict.get "a" d
3> Just 2
However, if you use foldr you will get Just 1 as the answer. Why? Because left fold, applies the values in the list from the left first, so in this example what you effectively get is:
1Dict.insert "a" 2 (Dict.insert "a" 1 Dict.empty)
For some this is a bit clearer using the right pizza |> operator, if you're not comfortable with that just ignore this code segment:
1Dict.insert "a" 1 Dict.empty
2 |> Dict.insert "a" 2
Either way you view it, it is clear that the insertion of the mapping from "a" to 2 is being inserted to the dictionary that already includes the mapping from "a" to 1 and therefore replaces that mapping. In this case whichever mapping is inserted into the empty dictionary is being inserted first, and will therefore be replaced when the other mapping is inserted. Because foldl applies items from the left first, the left most mapping is inserted into the empty dictionary and is thus replaced by the later mapping.
The foldr function applies elements of the list starting from the right:
1Dict.insert "a" 1 (Dict.insert "a" 2 Dict.empty)
1Dict.insert "a" 2 Dict.empty
2 |> Dict.insert "a" 1
So in this case it is the latter mapping which is inserted first and therefore which gets replaced.
Reversing a list with foldl #
This is sometimes easier to see if we use the cons operator as our function. The cons operator (::) is just a function with the type a -> List a -> List a so it can play the part of the function in a fold.
1> List.foldl (::) [] [1,2,3,4,5]
2[5,4,3,2,1 ]
3
4> List.foldr (::) [] [1,2,3,4,5]
5[1,2,3,4,5]
This is because the foldl function applies from the left first, so the first thing it does is cons 1 onto the empty list, ie. 1 :: [], it then takes the next element and cons that on, so 2 :: [1] and, then the next is consed on so 3 :: [2, 1] and so on. By contrast foldr recurses down to the end of the list first and then applies each element from the right, so the first cons foldr does is 5 :: [], and then the second last number is consed on to that list 4 :: [5] and then the third last element 3 :: [4, 5], and so on. So List.foldl (::) reverses a list whilst List.foldr (::) has no effect.
Some more folding examples #
The result of a fold does not need to be a larger data struction. For example you can return just a number, such as with the sum function, and very similarly the product function:
1sum : List number -> number
2sum l =
3 List.foldl (+) 0 l
4
5product : List number -> number
6product l =
7 List.foldl (*) 1 l
You can use a fold to search within a list, when you do so, you often need to inspect the list to check that it is not empty first, for example, here are definitions for minimum and maximum:
1min : number -> number -> number
2min x y =
3 if x < y then x else y
4
5max : number -> number -> number
6max x y =
7 if x < y then y else x
8
9minimum : List number -> Maybe number
10minimum l =
11 case l of
12 [] ->
13 Nothing
14 first :: rest ->
15 List.foldl min first rest
16 |> Just
17maximum : List number -> Maybe number
18maximum l =
19 case l of
20 [] ->
21 Nothing
22 first :: rest ->
23 List.foldl max first rest
24 |> Just
You can also use a fold to 'flatten' a data structure, such as flattening a list of lists into a single list:
1flatten : List (List a) -> List a
2flatten listOfLists =
3 List.foldr List.append [] listOfLists
Of course flatten is in the standard library as List.concat. Note that I'm using a foldr here, because with a foldl the elements would be reversed, an alternative would be to reverse the arguments to List.append:
1flatten : List (List a) -> List a
2flatten listOfLists =
3 let
4 flippedAppend left right =
5 List.append right left
6 in
7 List.foldl flippedAppend [] listOfLists
Which should I use? #
So the first thing is to decide which would give you the correct answer. The example above with the dictionary showed that you get two different answers depending on which you use. If you were doing this in a program would you want the key-value pairs at the start of the list to take precedence over those at the end of the list? If so, then use foldr but if not, then use foldl. But some of the examples we've seen are order independent. Such as sum, product, maximum and minimum. In a strict language such as Elm, if the order of applications does not matter, then you probably want to use foldl. Why?
This is to do with something called 'tail-recursion'. A 'tail-recursive' function is a function that is recursive, but that the last thing we do in the recursive case is call the function recursively. Because of this property the compiler can essentially turn your recursive function into a loop, which is faster than a set of recursive calls. Here is a tail-recursive function:
1isEven : Int -> Bool
2isEven i =
3 if i < 0
4 then isEven (abs i)
5 else case i of
6 0 ->
7 True
8 1 ->
9 False
10 _ ->
11 isEven (i - 2)
Note in both of the recursive calls, it is the very last thing that the function does before it returns. The key point is that you can just pretend that the recursive call is actually the original call, because when you return from the recursive call you are returning the same value from the current call. Here is a function that is not tail-recursive:
1length : List a -> Int
2length l =
3 case l of
4 [] ->
5 0
6 _ :: rest ->
7 1 + (length rest)
Notice how after the recursive call returns we have to modify the answer before returning from the current call, in particular we have to increment it by one. Now it is possible to transform such a function into a tail recursive one, but it's a little clunky:
1length : List a -> Int
2length outerList =
3 let
4 lengthAux soFar l =
5 case l of
6 [] ->
7 soFar
8 _ :: rest ->
9 lengthAux (soFar + 1) rest
10 in
11 length 0 outerList
Notice how now, the recursive call to lengthAux is indeed the very last thing that lengthAux does. So the lengthAux function is tail recursive. So now that we know that, lets look at the definitions for foldl and foldr, first from the left:
1foldl : (a -> b -> b) -> b -> List a -> b
2foldl f b elements =
3 case elements of
4 [] ->
5 b
6 (x :: xs) ->
7 foldl f (f x b) xs
Great, you see the last thing the function does before returning is make the recursive call. So when the recursive call returns we just return that value unchanged, hence this function is tail-recursive and can be optimised. Now foldr:
1foldr : (a -> b -> b) -> b -> List a -> b
2foldr f b elements =
3 case elements of
4 [] ->
5 b
6 (x :: xs) ->
7 f x (foldr f b xs)
Ach, here after we recurse, we have to apply the f function to the head of the list and the result of the recursive call, so foldr is not tail recursive. This function cannot be transformed in the same way that length could be. Ultimately you need to maintain a stack of the elements that you will later apply to the function.
One final point, I've seen code that either transforms a non-tail-recursive function into a tail-recursive one, or does something awkward in order to call List.foldl rather than List.foldr. In either case it might be the right thing to do if your function is likely to be called on a list with a large number of elements. If however you're writing a function that operates say on the list of children of a given person, then that list is unlikely to exceed double digits in length, hence your 'optimisation' is likely just both slower and more complicated for someone to comprehend. If on the other hand your list represents say the characters in a source code file, or pixels in an image, then making any functions that operate over it tail recursive may well be a major boon for performance, particularly in the cases you care about (eg. larger files).
For a lazy language, if the order does not matter then you probably want to use foldr, for reasons that are slightly beyond the scope of this post.