# Notes - Functional Programming MT22, Fold cheatsheet

> Source: https://ollybritton.com/notes/uni/prelims/mt22/functional-programming/notes/fold-cheatsheet/ · Updated: 2023-05-23 · Tags: uni, notes

- [Course - Functional Programming MT22](https://ollybritton.com/notes/uni/prelims/mt22/functional-programming/)

### Flashcards
Can you give the definition of `zip` as (almost) a fold?::
```haskell
zip' ;; [a] -> [b] -> [(a, b)]
zip' = foldr cons (const [])
     where cons x r [] = []
           cons x r (y:ys) = (x,y) : r ys
```

Can you give the definition of `map` as a fold?::
```haskell
map' ;; (a -> b) -> [a] -> [b]
map' f = fold (\x fxs -> f x: fxs) []
```

Can you give the definition of `filter` as a fold?::
```haskell
filter' p = fold (\x xs -> if p then x:xs else xs) []
```

Can you give the definition of `concat` as a fold?::
```haskell
concat = foldr (++) []
```

Can you give the definition of `(++ ys)` as a fold?::
```haskell
(++ ys) = foldr (:) ys
```

Can you give the definition of `takeWhile` as a fold?::
```haskell
takeWhile p = foldr cons []
	where cons x xs = if p x then x : xs else []
```

Given the definition of natural numbers as
```haskell
data Nat = Zero | Succ Nat
```
what is the natural fold?::
```haskell
foldN ;; (a -> a) -> a -> Nat -> a
foldN succ zero Zero = zero
foldN succ zero (Succ x) = succ (foldN succ zero x)
```

Can you give the Haskell type and corresponding fold for a binary tree with data at every node?::
```haskell
data Tree a = Null | Node a (Tree a) (Tree a)
foldT ;; b -> (a -> b -> b -> b) -> Tree a -> b
foldT null node Null = null
foldT null node (Node a left right)
	= node a (foldT null node left) (foldT null node right)
```

Can you give the Haskell type and corresponding fold for a binary tree with data only at the leaves?::
```haskell
data Tree a = Leaf a | (Tree a) `Fork` (Tree a)
foldT ;; (a -> b) -> (b -> b -> b) -> Tree a -> b
foldT leaf fork (Leaf a) = leaf a
foldT leaf fork (left `Fork` right) = fork
	(foldT leaf fork left)
	(foldT leaf fork right)
```

Can you define `cp` as a fold in Haskell?::
```haskell
cp ;; [[a]] -> [[a]]
cp = foldr (\a b -> [x:ys | x <- a, ys <- b]) [[]]
```

Can you give the definition of `permutations` as a fold in Haskell, using the following function `include`:
```haskell
include ;; a -> [a] -> [[a]]
include x = foldr cons [[x]]
	where cons a b = (x:a:tail (head b)) : map(a:) b
```
?::
```haskell
permutations ;; [a] -> [[a]]
permutations = foldr (concatMap . include) [[]]
```

Can you define a Haskell function `include x xs` that includes `x` in all possible positions in a list?::
```haskell
include ;; a -> [a] -> [[a]]
include x = foldr cons [[x]]
	where cons a b = (x:a:tail (head b)) : map(a:) b
```

Can you define a Haskell function `inits` that returns all the initial segments of a list as a fold, e.g. `inits [1,2,3]` is `[[], [1], [1,2], [1,2,3]]`?::
```haskell
inits ;; [a] -> [[a]]
inits = foldr cons [[]]
	where cons x xss = [] : map(x:) xss
```

Can you define `(++)` as a fold in Haskell?::
```haskell
(++) ;; [a] -> [a] -> [a]
(++) = foldr cons id
    where cons x y z = x:(y z)
```

---
Olly Britton — https://ollybritton.com. Machine-readable index: https://ollybritton.com/llms.txt