Michael Saelee

Feb 20, 2019

Let’s start by implementing the following functions and looking for a pattern:

```
sum' :: (Num a) => [a] -> a
sum' [] = 0
sum' (x:xs) = x + sum' xs
product' :: (Num a) => [a] -> a
product' [] = 1
product' (x:xs) = x * product' xs
and' :: [Bool] -> Bool
and' [] = True
and' (x:xs) = x && or' xs
or' :: [Bool] -> Bool
or' [] = False
or' (x:xs) = x || or' xs
stringify :: (Show a) => [a] -> String
stringify [] = ""
stringify (x:xs) = show x ++ stringify xs
```

Each of the above recursive functions has type `[a] -> b`

, and is built around two basic pieces:

- a value (of type
`b`

) associated with the base case (the empty list) - a function that takes a value from the list (of type
`a`

) and combines it with the value returned by the recursive call (of type`b`

) to compute the result (also of type`b`

)

I.e., to express a recursive list function of type `[a] -> b`

, we need:

- a combining function with type
`a -> b -> b`

- a base case value of type
`b`

Let’s design a HOF that encapsulates this notion of primitive list recursion:

We call this function “fold” — specifically, “fold right”.

Note: foldr is actually defined for the “Foldable” type class — the list is an instance of Foldable. We’ll see how this works later!

Intuitively, foldr applies the combiner function f to the last (i.e., rightmost) value in the list and the base value *first*, then works outwards, applying f to each list value and the result from the previous application of f, in turn.

E.g., foldr f z [1..5] = (1 `f`

(2 `f`

(3 `f`

(4 `f`

(5 `f`

z)))))

` = (f 1 (f 2 (f 3 (f 4 (f 5 z)))))`

Let’s define the above recursive functions in terms of foldr:

```
sum'' :: (Num a) => [a] -> a
sum'' = foldr (+) 0
product'' :: (Num a) => [a] -> a
product'' = foldr (*) 1
or'' :: [Bool] -> Bool
or'' = foldr (||) False
and'' :: [Bool] -> Bool
and'' = foldr (&&) True
stringify' :: (Show a) => [a] -> String
stringify' = foldr ((++) . show) ""
```

Try a few others:

```
(+++) :: [a] -> [a] -> [a]
l1 +++ l2 = foldr (:) l2 l1
length' :: [a] -> Int
length' = foldr (\_ r -> succ r) 0
```

And higher order functions:

```
map' :: (a -> b) -> [a] -> [b]
map' f = foldr ((:) . f) []
filter' :: (a -> Bool) -> [a] -> [a]
filter' f = foldr iter []
where iter x rst | f x = x : rst
| otherwise = rst
```

How about reverse?

Which translates into:

But this is inefficient! (Why?)

A better implementation of reverse is:

```
reverse''' :: [a] -> [a]
reverse''' xs = recur [] xs
where recur ys [] = ys
recur ys (x:xs) = recur (x:ys) xs
```

Note how the result (`ys`

) computed by `recur`

is built up (aka “accumulated”) from left to right over the input list. It is difficult (but not impossible!) to implement `reverse'''`

in terms of foldr.

In a left fold, we want to start by applying the combiner function to the base value and the first value in the list, then proceed onto succeeding values, so:

foldl f z [1..5] = (((((z `f`

1) `f`

2) `f`

3) `f`

4) `f`

5)

` = (f (f (f (f (f z 1) 2) 3) 4) 5)`

Determine the type of the left fold function and implement it:

Define reverse using foldl:

Which folds (if any) work with infinite lists?

Try:

Why?

Intuitively: - foldr’s combining function is applied to each element in turn (and to the recursive call) — this lets the combining function “short circuit” early - foldl builds up an accumulated value; the result is not known until all recursions are evaluated - foldl must recurse through the entire list to build up all the function applications before evaluating the *outermost* one

- foldl is
*left associative* - foldr is
*right associative* - foldr can work with infinite lists!

consider:

Following are true:

But following are not:

`-`

is left associative, and so should be evaluated using the left-fold.

`^`

is right associative, and should be evaluated using the right-fold.