Notes - Functional Programming MT22, Fold cheatsheet

Created: May 23, 2023

Flashcards

Can you give the definition of zip as (almost) a fold?

 
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?

 
map' ;; (a -> b) -> [a] -> [b]
map' f = fold (\x fxs -> f x: fxs) []

Can you give the definition of filter as a fold?

 
filter' p = fold (\x xs -> if p then x:xs else xs) []

Can you give the definition of concat as a fold?

 
concat = foldr (++) []

Can you give the definition of (++ ys) as a fold?

 
(++ ys) = foldr (:) ys

Can you give the definition of takeWhile as a fold?

 
takeWhile p = foldr cons []
	where cons x xs = if p x then x : xs else []

Given the definition of natural numbers as

data Nat = Zero | Succ Nat

what is the natural fold?

 
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?

 
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?

 
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?

 
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:

include ;; a -> [a] -> [[a]]
include x = foldr cons [[x]]
	where cons a b = (x:a:tail (head b)) : map(a:) b

?

 
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?

 
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]]?

 
inits ;; [a] -> [[a]]
inits = foldr cons [[]]
	where cons x xss = [] : map(x:) xss

Can you define (++) as a fold in Haskell?

 
(++) ;; [a] -> [a] -> [a]
(++) = foldr cons id
    where cons x y z = x:(y z)


Related posts