We use cookies and other tracking technologies to improve your browsing experience on our site, analyze site traffic, and understand where our audience is coming from. To find out more, please read our privacy policy.

By choosing 'I Accept', you consent to our use of cookies and other tracking technologies.

We use cookies and other tracking technologies to improve your browsing experience on our site, analyze site traffic, and understand where our audience is coming from. To find out more, please read our privacy policy.

By choosing 'I Accept', you consent to our use of cookies and other tracking technologies. Less

We use cookies and other tracking technologies... More

Login or register
to publish this job!

Login or register
to save this job!

Login or register
to save interesting jobs!

Login or register
to get access to all your job applications!

Login or register to start contributing with an article!

Login or register
to see more jobs from this company!

Login or register
to boost this post!

Show some love to the author of this blog by giving their post some rocket fuel 🚀.

Login or register to search for your ideal job!

Login or register to start working on this issue!

Login or register
to save articles!

Login to see the application

Engineers who find a new job through WorksHub average a 15% increase in salary 🚀

You will be redirected back to this page right after signin

Blog hero image

Catamorphisms aka folds explained

Marty Stumpf 22 April, 2021 | 4 min read

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 l:

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.

Aside: The Maybe type

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

Using 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.

Join our newsletter
Join over 111,000 others and get access to exclusive content, job opportunities and more!

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 Int.

We invoke foldr in findMinFold, which has the following type signature:

*Main> :t foldr
foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b

That is, foldr takes 3 inputs:

  • A function that takes two arguments, one of type a and one of type b, and returns a result of type b.
  • An input of type b.
  • An input of foldable type a.

In 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 foldr!

The second input is maxBound, of type:

Prelude> :t maxBound
maxBound :: Bounded a => a

Int is an instance of the Bounded typeclass. In findMinFold, maxBound is thus of type Int. Note that Integer and 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 maxBound:

fold_left min max_int [] => maxBound

  • When the list has one element, it returns the min of maxBound and the element:

foldr min maxBound [e1] => min e1 maxBound

  • When the list has two elements, min takes the result of ``(min e2 maxBound)`` as an input, and compare it with e1:

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 e1:

foldr min maxBound [e1,e2,e3] => min e1 (min e2 (min e3 maxBound))

and so on...

We can generalize it to any function f, with 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 foldr or 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 9223372036854775807:

*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!

Author's avatar
Marty Stumpf
Software engineer. Loves FP Haskell Coq Agda PLT. Always learning. Prior: Economist. Vegan, WOC in solidarity with POC.

Related Issues

open-editions / corpus-joyce-ulysses-tei
open-editions / corpus-joyce-ulysses-tei
  • Open
  • 0
  • 0
  • Intermediate
  • HTML
open-editions / corpus-joyce-ulysses-tei
open-editions / corpus-joyce-ulysses-tei
  • Open
  • 0
  • 0
  • Intermediate
  • HTML
open-editions / corpus-joyce-ulysses-tei
open-editions / corpus-joyce-ulysses-tei
  • Open
  • 0
  • 0
  • Intermediate
  • HTML
open-editions / corpus-joyce-ulysses-tei
open-editions / corpus-joyce-ulysses-tei
  • Open
  • 0
  • 0
  • Intermediate
  • HTML

Get hired!

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 Stack OverflowStart with Email