Catamorphisms aka folds explained
This is the fourth of a series of articles that illustrates functional programming (FP) concepts. As you go through these articles with code examples in Haskell (a very popular FP language), you gain the grounding for picking up any FP language quickly. Why should you care about FP? See this post.
In the last post, we learned about the foldable typeclass, which provides the
foldr method. In this post, we'll learn what this method is with an example.
As mentioned in earlier posts, we can treat recursions as separate higher order functions known as recursion schemes. One type of recursion scheme is catamorphisms (or fold in Richard Bird and Philip Wadler’s Introduction to Functional Programming).
Why Should I Care?
Because knowing how to use recursion schemes improves your coding ability! Consider this exercise: finding the minimum element of a list. In Haskell, without using fold, we would compare the elements of the list a one by one, keeping the minimum of the element, until we reach the end of the list. For example (interested readers can also see the OCaml version):
findMinInner :: Ord a => [a] -> a -> a findMinInner  curMin = curMin findMinInner (hd : tl) curMin = if hd < curMin then findMinInner tl hd else findMinInner tl curMin findMin :: Ord a => [a] -> Maybe a findMin  = Nothing findMin (hd:tl) = Just (findMinInner tl hd)
Using catamorphisms, we can find the minimum for an
Int list in two lines:
findMinFold :: [Int] -> Int findMinFold l = foldr (\x y -> if x < y then x else y) maxBound l
Or, using the function
min in the prelude to replace the anonymous function and eta-reducing
findMinFold :: [Int] -> Int findMinFold = foldr min maxBound
Catamorphisms dramatically reduce the amount of code because
foldr does exactly what we want it to do for us: recurse down each element of the list.
findMin returns a
Maybe a. The
Maybe a type is used when a type can be
Nothing. It either returns
Nothing or the value. In this case, when the input list is empty, the minimum element is nothing. Running the code in GHCi gives:
*Main> findMin [9,2,3,1] Just 1 *Main> findMin  Nothing
Maybe is not strictly necessary, Haskell's prelude (standard library) includes the
minimum function which throws an exception when an empty list is the input:
*Main> minimum  *** Exception: Prelude.minimum: empty list *Main> minimum [4,5,6,7,8] 4
findMinFold, on the other hand, returns the base case when the input list is empty.
How Does It Work?
Going back to the above example, what’s going on in that one line?
First, let us look at
findMinFold's type from GHCi:
Prelude> :t findMinFold findMinFold :: (Foldable t, Ord b, Bounded b) => t b -> b
findMinFold takes a foldable type
b and returns a result of type
b. More specifically, it takes a
[Int] and returns an
findMinFold, which has the following type signature:
*Main> :t foldr foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b
foldr takes 3 inputs:
- A function that takes two arguments, one of type
aand one of type
b, and returns a result of type
- An input of type
- An input of foldable type
findMinFold, we've given
foldr 2 inputs. The first is the function
min, of type:
Prelude> :t min min :: Ord a => a -> a -> a
min happens to have the second input type the same as the first, but bear in mind that it doesn't have to be as an input function to
The second input is
maxBound, of type:
Prelude> :t maxBound maxBound :: Bounded a => a
Int is an instance of the
Bounded typeclass. In
maxBound is thus of type
Int. Note that
Float are not bounded!
foldr recurses the function with the earlier result as an input. In this example,
foldr does the following:
- When the list is empty, it returns the
fold_left min max_int  => maxBound
- When the list has one element, it returns the
maxBoundand the element:
foldr min maxBound [e1] => min e1 maxBound
- When the list has two elements,
mintakes the result of ``(min e2 maxBound)`` as an input, and compare it with
foldr min [e1,e2] maxBound => min e1 (min e2 maxBound)
- When the array has three elements, min takes the result of
(min e3 maxBound)as an input to compare with
e2,the result of which is then compared to
foldr min maxBound [e1,e2,e3] => min e1 (min e2 (min e3 maxBound))
and so on...
We can generalize it to any function
z as the starting case and
x as the list input, the result is as in the prelude with
f as an infix operator:
foldr f z [x1, x2, ..., xn] == x1 `f` (x2 `f` ... (xn `f` z)...)
foldl works similarly, except that the list elements are the first input to the function, and the brackets are to the left:
foldl f z [x1, x2, ..., xn] == (...((z `f` x1) `f` x2) `f`...) `f` xn
The Base Case
You can see from the above example that to find the minimum element of a list, we can use
foldl, naturally with the
min function as the function input. But how do we choose the base case input?
The base case is what fold returns on an empty list input. When the input to
findMinFold is an empty list, the base case is returned. As you can see from GHCi, the maximum
Int on my system is
*Main> findMinFold  9223372036854775807
Other examples are:
-- adding 0 and x returns x sum :: (Foldable t, Num a) => t a -> a sum = foldr (+) 0 -- multiplying 1 and x returns x product :: (Foldable t, Num a) => t a -> a product = foldr (*) 1
Because the base case to
foldr is only there to safe guard an empty input, when you can be sure that the input is not empty, the base case would not be necessary! Haskell provides such option. We’ll see this in the next post, along with more examples of folds!
Sign up now and apply for roles at companies that interest you.
Engineers who find a new job through WorksHub average a 15% increase in salary.Start with GitHubStart with TwitterStart with Stack OverflowStart with Email