Feb 20, 2019

# Primitive Recursion

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:

1. a value (of type `b`) associated with the base case (the empty list)
2. 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:

``````recur :: (a -> b -> b) -> b -> [a] -> b
recur f z [] = z
recur f z (x:xs) = f x \$ recur f z xs``````

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

# Fold Right

``foldr :: (a -> b -> b) -> b -> [a] -> b``

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``````

``````reverse' :: [a] -> [a]
reverse' [] = []
reverse' (x:xs) = reverse' xs ++ [x]``````

Which translates into:

``````reverse'' :: [a] -> [a]
reverse'' = foldr (flip (++) . (:[])) []``````

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.

# Fold Left

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:

``````foldl' :: (b -> a -> b) -> b -> [a] -> b
foldl' _ z [] = z
foldl' f z (x:xs) = foldl' f (f z x) xs``````

Define reverse using foldl:

``````reverse'''' :: [a] -> [a]
reverse'''' = foldl (flip (:)) []``````

# On Infinite Lists

Which folds (if any) work with infinite lists?

Try:

``````take 10 \$ foldr (:) [] [1..]
foldr (||) False \$ map even [1..]
foldl (||) False \$ map even [1..]``````

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

# Which Fold?

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

consider:

``````foldl1' :: (a -> a -> a) -> [a] -> a
foldl1' f (x:xs) = foldl f x xs``````
``````foldr1' :: (a -> a -> a) -> [a] -> a
foldr1' f [x] = x
foldr1' f (x:xs) = f x \$ foldr1' f xs``````

Following are true:

``````foldl1 (+) [1..10] == foldr1 (+) [1..10]
foldl1 (*) [1..10] == foldr1 (*) [1..10]``````

But following are not:

``````foldl1 (-) [10, 2, 1, 3] == foldr1 (-) [10, 2, 1, 3]
foldl1 (^) [2, 3, 4] == foldr1 (^) [2, 3, 4]``````

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

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