After revising this lecture, please read this terrifyingly beautiful review paper: A Tutorial on the Universality and Expressiveness of Fold by Graham Hutton.

But first, meet Ackermann. And go watch 'Mr Robot' later.

hackermann

In [7]:
-- a fold on a list to get the sum of all elements
foldr (+) 0 [1, 2, 3, 4, 5]
Use sum
Found:
foldr (+) 0
Why Not:
sum
15
In [14]:
{-# LANGUAGE DeriveFoldable #-}

-- a fold on a tree to get the sum of all elements
data Tree a = Leaf | Node (Tree a) a (Tree a) deriving Foldable

In [18]:
t = Node (Node (Node Leaf 1 Leaf) 2 (Node Leaf 5 Leaf)) 7 (Node Leaf 10 Leaf)
In [19]:
foldr (+) 0 t
Use sum
Found:
foldr (+) 0
Why Not:
sum
25

markdown

In [21]:
:t foldr
foldr :: forall (t :: * -> *) a b. Foldable t => (a -> b -> b) -> b -> t a -> b
In [22]:
:t (+)
(+) :: forall a. Num a => a -> a -> a
In [23]:
foldr (+) 1 [1, 2, 3]

7
In [27]:
data List a = Nil | Cons a (List a) deriving Foldable
In [28]:
l = Cons 1 (Cons 2 (Cons 4 Nil))
In [30]:
sum l

7
In [35]:
1 : 2 : 3 : []
Use list literal
Found:
1 : 2 : 3 : []
Why Not:
[1, 2, 3]
[1,2,3]
In [37]:
1 + (2 + (3 + 1))

7
In [18]:
sum [1, 2, 3]
length [1, 2, 3]
id [1, 2, 3]
reverse [1, 2, 3]
map (*3) [1, 2, 3]
filter (>2) [1, 2, 3]

6
3
[1,2,3]
[3,2,1]
[3,6,9]
[3]
In [19]:
foldr (\x y -> x + y) 0 [1, 2, 3]
foldr (\x y -> 1 + y) 0 [1, 2, 3]
foldr (\x y -> x:y) [] [1, 2, 3]
foldr (\x y -> y ++ [x]) [] [1, 2, 3]
foldr (\x y -> (3*x):y) [] [1, 2, 3]
foldr (\x y -> if x>2 then x:y else  y) [] [1, 2, 3]
Avoid lambda
Found:
\ x y -> x + y
Why Not:
(+)
Use map
Found:
foldr (\ x y -> x : y) []
Why Not:
map (\ x -> x)
Avoid lambda
Found:
\ x y -> x : y
Why Not:
(:)
Use map
Found:
foldr (\ x y -> (3 * x) : y) []
Why Not:
map (\ x -> 3 * x)
6
3
[1,2,3]
[3,2,1]
[3,6,9]
[3]
In [13]:
((+1) . sum) [1, 2, 3]

7
In [ ]: