Fold function in haskell

let’s first take a look at some list functions, and see what’s the characteristic they all share

• sum: computes the sum of the numbers of a structure;
• and: returns the conjunction of a container of Bools;
• map: map f xs is the list obtained by applying f to each element of xs.

There three are all common list function, and act very differently, but can be defined recursively using pattern matching as follow:

mySum :: (Num t) => [t] -> t
mySum []       = 0              -- sum of empty is 0
mySum (x : xs) = x + mySum xs   -- otherwise, add first element to sum of rest of the list

myAnd :: [Bool] -> Bool
myAnd [] = True                 -- and of empty is True
myAnd (x : xs) = x && myAnd xs  -- otherwise, return the conjunction of first element and the rest of list

myMap :: (t -> t) -> [t] -> [t]
myMap _ []       = []               -- map any function to empty is empty
myMap f (x : xs) = f x : myMap f xs -- otherwise, prepends f of first element to map f of rest of list

Here we can see the common pattern: Each of them has a binary operator, a starting value (typically the right-identity of the operator), and a list:

• in sum function, they are +, 0 and the list;
• in and function, they are &&, True and the list;
• in map function, things is a litter complicate, but we can still find them: (\x xs -> (f x):xs), [] and the the list.

In Haskell, we have a high order function which applied to a binary operator, a starting value (typically the right-identity of the operator), and a list, reduces the list using the binary operator, from right to left:

foldr f z [x1, x2, ..., xn] == x1 `f` (x2 `f` ... (xn `f` z)...)

So we can rewrite sum, and and map use foldr like this:

mySum' :: (Num t) => [t] -> t
mySum' xs = foldr (+) 0 xs

myAnd' :: [Bool] -> Bool
myAnd' xs = foldr (&&) True xs

myMap' :: (t -> t) -> [t] -> [t]
myMap' xs = foldr (\x xs -> (f x):xs) [] xs

It’s way much easier for us to understand.
That’s all for today, happy coding!