According to Wikipedia a catamorphism “denotes the unique homomorphism from an initial algebra into some other algebra”.
Uh huh. Sure.
I’ve got an admittedly very basic understanding of this concept, but I thought I’d share the small amount I have been able to learn and apply, as I’ve found it to be a useful tool for working with types.
Cat a what?
The word catamorphism comes from the Greek κατά, meaning “downwards”, and “morphism” which we tend to use to mean “transformation”. So it’s a transformation that takes something down, or reduces something.
What’s this mean in terms of functional programming? Remember from a while back, an endomorphism, or “inside transformation”, transforms a value of some type into a value of the same type? Well a catamorphism takes a value of a type with some structure, and reduces that to a value of another type.
Call me Option
To explore this idea, let’s define our own version of the
A value of this type can either be
Full someValue. Now let’s say we want to convert an
Option a to some type
b. We need to get at the structure of our
Option type, and work out how to convert each alternative to a
b. We can do this using pattern matching:
The first argument to
option is the default value of type
b that will be returned when the option is
Empty. The second argument is a function that will convert the value in a
Full value to a
b. The final argument is the option we are reducing.
We then have two patterns to match for
Option a values. The first pattern is matched when the option is
Empty, in which case the default value is returned. The second pattern is when we have a
Full value, where we return the result of applying the function from the second argument
f to that value. Here’s a quick example of it in action:
ghci> option "empty" show (Full 42) "42" ghci> option "empty" show Empty "empty"
So we’ve taken a type that has two possible components, and
Full value, and created a function that transforms it into a type with a potentially reduced number of components. A downward transformation. A catamorphism. And we can now use this transformation to break apart our
Option type without having to repeat that pattern matching everywhere.
maybefunction that works the same way for the
Catamorphisms and identity
Catamorphisms have an interesting property: if we use the type’s value constructors as arguments to the type’s catamorphism, we get the identity function for that type.
Option type has two value constructors. We can construct a value of type
Option a using the
Empty constructor, or using
Full value. Let’s use these as arguments to the
ghci> :t Empty Empty :: Option a ghci> :t Full Full :: a -> Option a ghci> :t option option :: b -> (a -> b) -> Option a -> b ghci> option Empty Full (Full 42) Full 42 ghci> option Empty Full (Empty) Empty ghci> quickCheck $ \x -> id x == option Empty Full x +++ OK, passed 100 tests.
Whatever value we pass to
option Empty Full, we always get the same value back. This is a result of the
option catamorphism deconstructing the
Option type, so feeding in the constructors for that type reconstructs the type unchanged.
We can follow this pattern of matching value constructors to implement a catamorphism for any type:
The list catamorphism
To finish up, let’s look at a very well known catamorphism. In Haskell there are two ways to construct a list. The first is to use
: (cons) to add an element to an existing list,
x : list. The second is using the empty list constructor
. Now let’s have a look at this function:
The first two arguments to fold right match the value constructors for lists. The first takes a list item and a
b used for accumulating the result of recursive calls, mirroring the calls used to construct the list. The second is the value used in the case of the empty list
ghci> quickCheck $ \x -> id x == foldr (:)  x +++ OK, passed 100 tests.
Which is why
foldr is also know as the list catamorphism.
Catamorphisms, at least as I understand them, aren’t nearly as frightening as they sound. A catamorphism for a type is function for transforming it, deconstructing the type into its components and providing us the option to reduce the type to a simpler structure (reduced number of components). One result of this is that plugging in the type’s value constructors will reassemble the type, giving us an identity function for the type.
If you’ve read any of my posts on list folds you’ll probably have some appreciation for how useful catamorphisms can be. Whereas
foldr lets us encapsulate list recursion, catamorphisms for other types like
Option) let us deal with the constituent parts of a type, without having to repeat pattern matching on the type every time we wish to transform it.
Hope you found this interesting! As always, please ask away if you have any questions or if I’ve failed to explain something adequately.