Haskell: folding : foldl, foldr functions

In my previous post, I explained about fold pattern, in this post I am going to explain about the foldl, foldr functions in detail. Generally fold patterns are used to process some data structure and return a value.

Fold function

A typical fold function takes two arguments.

a.   Function to combine elements of a data structure.

b.   A data structure that contains elements, usually list of elements.

For example,

fold (*) [1,2,3,4,5] calculates 1 * 2 * 3 * 4 * 5 = 120.

In general there are two ways to implement fold function.

a.   left fold (foldl)

b.   Right fold (foldr)

Left fold (foldl) : Folding from left

‘foldl’ performs folding from left. Following is the implementation of fold left function.

FoldUtil.hs

foldleft :: (a -> b -> a) -> a -> [b] -> a
foldleft fun accumulator []     = accumulator                  
foldleft fun accumulator (x:xs) = foldleft fun (fun accumulator x) xs

foldleft function takes a function and an initial accumulator value to accumulate the result. The function takes an accumulator and an element from list, return new accumulator value. As you observe, foldleft function consumes the elements of list from left to right.

*Main> :load FoldUtil.hs
[1 of 1] Compiling Main             ( FoldUtil.hs, interpreted )
Ok, modules loaded: Main.
*Main> 
*Main> foldleft (+) 0 [1, 2, 3, 4, 5]
15
*Main> 
*Main> foldleft (*) 1 [1, 2, 3, 4, 5]
120
*Main>

Right fold (foldr) : Folding from right

It is just opposite to fold left (foldl) function. It folds data from right to left. Following is the implementation of fold right function.

FoldUtil.hs  

foldright :: (a -> b -> b) -> b  -> [a] -> b
foldright fun accumulator []     = accumulator                  
foldright fun accumulator (x:xs) = fun x (foldright fun accumulator xs)

*Main> :load FoldUtil.hs
[1 of 1] Compiling Main             ( FoldUtil.hs, interpreted )
Ok, modules loaded: Main.
*Main> 
*Main> foldright (+) 0 [1, 2, 3, 4, 5]
15
*Main> foldright (*) 1 [1, 2, 3, 4, 5]
120

Observe the implementation of foldright function, it folds the value of a list from right to left.

Previous                                                 Next                                                 Home