Fold operator - a brief detour

This article aims to be a brief practical introduction to new haskell programmer about the fold high order function (which roughly speaking is a function that takes as input and/or produces as output a function) and its usage. It will also outline a bit of the theory that lies behind this operator (the term operator comes from the field of recursion theory (Kleene, 1952), even if, striclty speaking fold is a function in haskell).

Haskell Fold - Introduction and formal definition

Many problem in function programming are solved by means of tail recursive functions (one that do not perform any other operations that need some values from the recursive call). For instance let's say we want to get the product of integers stored in a list.
What we would do is to write down a tail recursive function (more or less) like this

tailmultiply :: [Int] -> Int -> Int
tailmultiply [] acc     = acc
tailmultiply (x:xs) acc = tailmultiply xs (acc * x)

Note, to stress the tail recursion, a definition like the one that follows would not be tail recursive.

--No tail recursive version
notailmultiply :: [Int] -> Int
notailmultiply [] acc     = 1  --neutral element for multiplication
notailmultiply (x:xs) acc = x * notailmultiply xs

as the recursive call is used for the multiplication (this implies that we need a sort of stack representation of recursive call, but this is another story).

Let's say now that we want to compute the sum of the numbers, we cannot somehow reuse the function for the multiplication and we should write down another function definition that look more or less the same of the previous one.

tailsum :: [Int] -> Int -> Int
tailsum [] acc     = acc
tailsum (x:xs) acc = tailsum xs (acc + x)

As before the same recursion patter appear, we have an edge case concerning the empty list the a tail recursive step over a non-empty list. It turn out that this patter is effective and natural when addressing a great number of problems. Here that fold operator comes to help, because it encapsulate this pattern and allow us to concentrate and limitate our writing efforts just to the core operation we want to perform on the list. To be precise, two family of fold exists, left and right fold(foldl and foldr respectively left and right associative ). The former straightfowardly extend the recursive patter seen before, but as it will turs out later on, it is less powerful (in terms of problem can solve) than his right version (that we can use to write the left version).

Let's start with the foldl that is defined as follow:

foldl :: (b -> a -> b) -> b -> [a] -> b
foldl _ acc []       = acc
foldl f acc (x:xs)   = foldl f (f acc x) xs

It is a function that takes as input a binary function an initial value for the accumulator and the list to operate on. The edge case here use the wildcard to stress the fact that the binary function is not applied. It consumes the list and store the partial result at each recursive call in the accumulator function (exactly as in the multiplication and sum examples). It allow use to easily rewrite out sum and product function as follow:

foldproduct :: [Int] -> Int
foldproduct = foldl (*) 1

foldsum :: [Int] -> Int
foldsum = foldl (+) 0

which looks now more coincise and elengantly written, even if at first sight a bit cryptic.
Just to show a bit more sophisticated example we are gonna redifine the map function in terms of foldl. Remaind that the map takes a function and applies it to all the elements of the list:

map :: (a -> b) -> [a] -> [b]
map f = foldl (\acc x -> f  acc ++ [f x]) []

Note that the accumulator value for fold can be anything, in this case is a list, but could even be functions (it would be the case when writing foldl in terms of foldr) or whichever type comes in your mind. Note also that map would implemented more efficenltly using a right fold (and you should always use foldr when producing list out of a fold call) as we will see later (++ operator is more costly compared to the cons operator : we will use) but is works for the purpose of showing this concept.

Right fold

Righ fold is right associative, and roughly speaking it means that consumes the list from the right. (see the images , from wikipedia, for a graphical explanation of the differences between foldr e foldl)


The foldr operator is defined as follow (this patter should look familiar now):

fold :: (a -> b -> b )  -> b -> [a] -> b
fold _ v []     = v
fold f v (x:xs) = f x (fold f v xs)

it takes a binary function as foldl does but in reverse order (i.e. takes as first parameter an element from the list and an accumulator as second), an initial value and the list that has to consumes. There is a nice and intuitive explaination of how foldr works i.e., it traverse the list to the end and substitute the empty list constructor at the end of the input list with the parameter v, and each cons operator with an application of f.
Suppose we want to write down our version of standard prelude filter function which takes a functions (a predicate test) of type (a -> Bool) and returns a sublist of the input list made of all the elements that satisfy the predicate:

filter :: (a -> Bool) -> [a] -> [a]
filter _ [] = []
filter f (x:xs)
   | f x       = x : filter xs
   | otherwise = filter xs

Our foldr filter function would looks like this:

filterwithfoldr :: (a -> Bool) -> [a] -> [a]
filterwithfoldr p  = foldr f []
   where f x acc = if p x then x:acc else acc

Let's say we want to filter out of a list of integers all the elements that are even. Obviously we should invoche something like filter (even) [1,2,3,4,5]. We know that foldr will start from the rightmost element (5) testing the p predicates on it (in out case if it is even) and if it is satisfied simply puts the value into the to be returned accumulator value and so on until we consume the whole list.

Let's track an execution of the filterwithfoldr function on the list [1..5]
filter (even) [] 1:2:3:4:(5:[])
(p 5 fails) filter (even) [] 1:2:3:4 do not push anything into the accumulator
(p 4 ok) filter (even) [4] 1:2:3:4 , 4 should be returned as result of filter
(p 3 fails) filter (even) [4] 1:2:3 again 3 fails, so discard it
(p 2 ok) filter (even) [2,4] 1:2 obsiously 2 is even, so keep it
(p 1 fails) filter (even) [4] 1 one is odd
(empty list) filter (even) [2,4] => finally we return the accumulator

Here a list some of few simple functions and their definition with foldr/foldl:

--prelude any
myAny :: (a->Bool) ->[a] -> Bool-> Bool
myAny f [] acc     = acc
myAny f (x:xs) acc = myAny f xs (f x || acc)

myAnyFold :: (a -> Bool) -> [a] -> Bool
myAnyFold p  = foldr step False
        where step x acc = (p x) || acc

--prelude takewhile
myTakeWhile :: (a->Bool) ->[a]-> [a] ->[a]
myTakeWhile f [] acc = acc
myTakeWhile f (x:xs) acc
     |f x     = myTakeWhile f xs (acc++[x])
     |otherwise = acc

myTakeWhileFoldr :: (a->Bool) -> [a] -> [a]-> [a]
myTakeWhileFoldr p  = foldr f id
        where f  = (\ x y -> (\ acc -> if p x then y (acc++[x]) else acc))

--prelude cycle
myCycle :: [a]->[a]
myCycle l = l ++ myCycle l

myCycleFold :: [a]->[a]
myCycleFold l = foldr step n l
           n = l ++ myCycleFold l
           step x acc=  x:acc

Use fold to produce tuples

Suppose you have a list of elements you want to calculate k functions on them. It could be the case of a list of integers for which you need to compute the product, sum, average, max, min ... Each of these function requires you to loop over all the element of the list, with a total cost of O(kn). Using fold you can consume the list only once and produce a tuple that store at each location i the result of the function f_i on the list. How can we do it? We will fist see an example and then try to generalize this method.
Let's so write a function for computing both sum and products of a list of integers. It has to return a tuple, hence not surprisingly the initial value is a tuple which component are the initial value of the corrensponding f_i fold definition (in this caso 0 for the sum and 1 for the product).

sumproductfold :: [Int] -> (Int,Int)
sumproductfold = foldr f (0,1)
 where f x (ss,pp) = (ss+x,pp*x)

More in general suppose you have k functions (that can be defined with fold obviously)
f_1 = fold\: (step_1)\: v_1 , f_2 = fold \: (step_2)\: v_2 , ... , f_k = fold \:(step_k)\: v_k
One can always write a function f_s the computes a tuple (r_1,r_2,...,r_k) s.t. r_i=fold \:step_i \:v_i
using just one application of fold (hence traversing the list only once) where,
f_s = fold \:step_s \:v_s and step_s \:x \:(v_1,..,v_k) = (f_1 \:x \:v_1, ... , f_k \:x \:v_k)

Conclusion on haskell fold functions

Writing function and programs that use fold is a good habit that every haskell programmer should start to take, even if it requires a bit of practice and experience expecially for haskell novices(at least it was so for me). Fold is very well understood by the haskell community, and its behaviour is somehow more predictable than a recursive function that force us to step into the details of the function we are trying to read and undestand (general recursion can do anything). Moreover as a side effect your code will be less error prone (you know how fold operates).

In one of the next article we will address, a techniques (from Hutton's paper, a  very well written paper about fold) that help in converting "canonical" tail recursive function into ones that use fold using the so called universality property that uncoinsciously used in some of the example provided in this article.

Be the first to leave a comment. Don’t be shy.

Join the Discussion

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>