Among all the beautiful higher order functions
there is one family that I think shines a little brighter than the rest: *the folds*.

`fold`

is a function that takes three arguments: *a binary function, a base value* and *a list*. When `fold`

is applied to its arguments the binary function is inserted between the elements of the list like so:

`fold op base [a, b, c] => a `op` b `op` c `op` base`

`fold`

is named so since it *folds* the elements of the list onto each other. `fold`

is also commonly known as *reduce* since it usually reduces a list to a single value.

`fold`

comes in two different flavors, `foldr`

and `foldl`

, depending on if the function associates to the right or left respectively.

`fold`

r`op base [a, b, c] => a `op` (b `op` (c `op` base))`

`fold`

l`op base [a, b, c] => ((base `op` a) `op` b) `op` c`

#### foldr

-- foldr in Haskell-- natural recursion until it reaches the empty list where the base value is returned-- Arguments-- The binary function (a -> b -> b) takes two arguments and returns a value of the second arguments type.-- The base value (b) must be of the same type as the binary funtions second argument and return type.-- The list [a] must be of the same type as the first argument of the function.foldr:: (a -> b -> b) -> b -> [a] -> bfoldr op base [] = base foldr op base (x:xs) = x `op`(foldr op base xs)

So, what is the big deal with fold? I can express almost any list manipulation with fold.

-- Sum up all elements of list.sum:: Num a => [a] -> asum xs = foldr (+) 0 xs-- sum [1, 2, 3]-- (foldr (+) 0 [1, 2, 3])-- 1 + (foldr (+) 0 [2, 3])-- 1 + 2 + (foldr (+) 0 [3]))-- 1 + 2 + 3 + foldr (+) 0 []))-- 1 + 2 + 3 + 0-- 6-- And, check if all elements of a list are Trueand:: [Bool] -> Booland xs = foldr (&&) True xs

The declaration of id_list below shows an example of an application of a funtion `(:)`

that is not type-symmetrical. The type of `(:)`

is: `a -> [a] -> [a]`

and care must be taken to provide the elements in correct order.

-- The identity function for listid_list:: [a] -> [a]id_list = foldr (:) []-- id_list [1, 2, 3]-- (foldr (:) [] [1, 2, 3])-- 1 : (foldr (:) [] [2, 3])-- 1 : 2 : (foldr (:) [] [3]))-- 1 : 2 : 3 : foldr (:) [] []))-- 1 : 2 : 3 : []-- [1, 2, 3]-- Map a function to all elements of a listmap:: (a -> b) -> [a] -> [b]map f xs = foldr (\a b -> f a : b) [] xs-- All, check if all elements of a list are true according to predicate pall:: (a -> Bool) -> [a] -> Boolall p xs = and (map p xs)

#### foldl

To complement `foldr`

we have `foldl`

which is similar but associates to the left instead of to the right. This is sometimes useful since it allows us to process the elements of the list in the opposite order.

-- foldl in Haskell-- Applies the base to first element of the list, the value is accumulated and used a base.-- Arguments-- The binary function (a -> b -> a) takes two arguments and returns a value of the first arguments type.-- The base value (a) must be of the same type as the binary funtions first argument and return type.-- The list [b] must be of the same type as the second argument of the function.foldl:: (a -> b -> a) -> a -> [b] -> afoldl op base [] = base foldl op base (x:xs) = foldl op (base `op` x) xs-- Multiplies all elements of list.sum:: Num a => [a] -> asum xs = foldr (*) 1 xs-- prod [1, 2, 3]-- (foldl (*) 1 [1, 2, 3])-- (foldl (*) (1 * 1) [2, 3])-- (foldl (*) (1 * 1 * 2) [3])-- (foldl (*) (1 * 1 * 2 * 3) [])-- 1 * 1 * 2 * 3-- 6

Since `foldl`

processes the elements from left to right it may be used to reverse a list. The first try to do this is the same as the identity functon above but with `foldl`

instead of `foldr`

.

-- The erroneous reverse function for listserr_rev:: [a] -> [a]err_rev = foldl (:) []---*** Expression : foldl (:) []---*** Term : (:)---*** Type : a -> [a] -> [a]---*** Does not match : [a] -> [a] -> [a]---*** Because : unification would give infinite type

The problem comes from the order in which the arguments are applied. When the function is applied it reduces to:

-- rev [1, 2, 3]-- (foldl (:) [] [1, 2, 3])-- (foldl (:) ([] : 1) [2, 3]) -- error since the (:)-functions argument are applied in reverse order.

We need to reverse the arguments to the function and this can be done through the simple function `flip`

.

-- Flip takes a function as parameter and returns the function with the arguments reversed.flip:: (a -> b -> c) -> b -> a -> cflip f x y = f y x-- The correct reverse function for listrev:: [a] -> [a]rev = foldl (flip (:)) []-- rev [1, 2, 3]-- (foldl (flip (:)) [] [1, 2, 3])-- (foldl (flip (:)) ([] (flip (:)) 1) [2, 3])-- (foldl (flip (:)) (([] (flip (:)) 1) (flip (:)) 2) [3])-- (foldl (flip (:)) ((([] (flip (:)) 1) (flip (:)) 2) (flip (:)) 3) [])-- ((([] (flip (:)) 1) (flip (:)) 2) (flip (:)) 3)-- (((1 : []) (flip (:)) 2) (flip (:)) 3)-- ((2 : [1]) (flip (:)) 3)-- (3 : [2, 1])-- [3, 2, 1]

#### foldr1 and foldl1

For lists that are known to be non empty and that work on a single type there are two simplified versions of `fold`

called `foldr1`

and `foldl1`

that do not need a base case passed as argument. This makes them simpler to use but also less powerful.

-- foldr1 in Haskell for non-empty lists-- Arguments-- (a -> a -> a) A binary function operating on a single type.-- [a] A list containing this typefoldr1:: (a -> a -> a) -> [a] -> afoldr1 f [x] = x foldr1 f (x:xs) = f x (foldr1 f xs)-- Return the largest element of two.max:: Ord a => a -> a -> amax x y | x >= y = x | otherwise = y-- Return the largest elements of a listmaximum:: Ord a => [a] -> amaximum xs = foldr1 max xs

`foldl1`

is defined similarily.

If you want to check out the folds on the web, here are two sites that will allow you to explore them: foldl.com and foldr.com. Click the ellipsis… :)

## No comments:

Post a Comment