20.md

Higher order functions

Foldl

Let's compare the type of left fold with the type of right fold.

foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b
foldl :: Foldable t => (b -> a -> b) -> b -> t a -> b

The only visible difference is in the type of the combinator function. The function's first parameter is the already combined value and the second parameter is the next value from the foldable. Now let's see how it works.

Try out the following in ghci.

f :: (Show a, Integral a) => a -> String -> String
f n acc
  | even n = (show n) ++ acc
  | otherwise = acc

g :: (Show a, Integral a) => String -> a -> String
g acc n
  | even n = acc ++ (show n)
  | otherwise = acc

foldr f "" [1..6]
foldl g "" [1..6]

g is the same function as f with swapped parameters to conform to foldl and accumulator is on the left side of concatenation operator. To emphasize the difference between the two folds, let's run the following.

foldr f "!" [1..6]
foldl g "!" [1..6]

So foldl would do something like this:

--foldr
(show 2 ++ (show 4 ++ (show 6 ++ "!")))

-- foldl
((("!" ++ show 2) ++ show 4) ++ show 6)

Exercise

• Write the mysum :: (Num a, Foldable t) => t a -> a function.

Extra exercise

• Implement myfoldl.

Which fold should I use?

It is a hard question, and I can not give a complete answer to it because we have not talked about lazy evaluation, which is a key factor. For now follow these guidelines:

• If the foldable is an infinite structure you should use foldr. We have not seen any infinite data structure so far. You can start playing in ghci with repeat, take, cycle to have a basic understanding.
• If the foldable is finite and it needs to be evaluated always completely, import Data.List and use foldl' which is identical to foldl.