Lecture 16-2
Fold Continued
A fold output can be a different type to the input list.
to_csv list = foldr (\x acc -> show x ++ "," ++ acc) "" list
> to_csv [1,2,3,4]
> "1,2,3,4,"
By using foldr you cannot get the desired outcome as it applies the same rule to every item in the list.
foldr1
The function foldr1 uses the final value of the list to initialise the accumulator:
foldr1 :: (a -> a -> a) -> [a] -> a
foldr1' _ [] = error "empty list"
foldr1' -[x] = x
foldr1' f (x:xs) = f x (foldr1' f xs)
> foldr1' (+) [1,2,3,4,5]
> 15
As the accumulator has the same type as the list elements foldr1 cannot have a different type to that of the elements in the list.
Example
maximum' list = foldr1 (\ x acc -> if x > acc then x else acc) list
> maximum [1,2,3,4,3,2,1]
> 4
In this example foldr1 is required as your initialisation may become the maximum value.
foldl
foldr processes lists from the right. The opposite of this is foldl which processes lists from the left. For many functions like + the ordering doesn’t matter but for other functions such as /.
Type of foldl
The function f has its type flipped compared to the other fold function:
foldr :: (a -> b -> b) -> b -> [a] -> b
foldl :: (b -> a -> b) -> b -> [a] -> b
This also means that you should swap your functions:
foldr (\ x acc -> ...foldr (\ acc x -> ...
Example
reverse_list list = foldl (\ acc x -> x : acc) [] list
> reverse_list [1,2,3,4]
> [4,3,2,1]
Exercises
sumFsts list = foldr (\ (x,_) acc -> x + acc) 0 listminimum list = foldr1 (\ x acc -> if x < acc then x else acc) listdash string = foldl (\ acc x -> acc ++ [x, '-']) "" string