The catamorphism for Peano numbers involves a base value and a successor function.

This article presents the catamorphism for natural numbers, as well as how to identify it. The beginning of the article presents the catamorphism in C#, with examples. The rest of the article describes how I deduced the catamorphism. This part of the article presents my work in Haskell. Readers not comfortable with Haskell can just read the first part, and consider the rest of the article as an optional appendix.

### C# catamorphism #

In this article, I model natural numbers using Peano's model, and I'll reuse the Church-encoded implementation you've seen before. The catamorphism for `INaturalNumber` is:

```public static T Cata<T>(this INaturalNumber n, T zero, Func<T, T> succ)
{
return n.Match(zero, p => p.Cata(succ(zero), succ));
}```

Notice that this is an extension method on `INaturalNumber`, taking two other arguments: a `zero` argument which will be returned when the number is zero, and a successor function to return the 'next' value based on a previous value.

The `zero` argument is the easiest to understand. It's simply passed to `Match` so that this is the value that `Cata` returns when `n` is zero.

The other argument to `Match` must be a `Func<INaturalNumber, T>`; that is, a function that takes an `INaturalNumber` as input and returns a value of the type `T`. You can supply such a function by using a lambda expression. This expression receives a predecessor `p` as input, and has to return a value of the type `T`. The only function available in this context, however, is `succ`, which has the type `Func<T, T>`. How can you make that work?

As is often the case when programming with generics, it pays to follow the types. A `Func<T, T>` requires an input of the type `T`. Do you have any `T` objects around?

The only available `T` object is `zero`, so you could call `succ(zero)` to produce another `T` value. While you could return that immediately, that'd ignore the predecessor `p`, so that's not going to work. Another option, which is the one that works, is to recursively call `Cata` with `succ(zero)` as the `zero` value, and `succ` as the second argument.

What this accomplishes is that `Cata` keeps recursively calling itself until `n` is zero. The `zero` object, however, will be the result of repeated applications of `succ(zero)`. In other words, `succ` will be called as many times as the natural number. If `n` is 7, then `succ` will be called seven times, the first time with the original `zero` value, the next time with the result of `succ(zero)`, the third time with the result of `succ(succ(zero))`, and so on. If the number is 42, `succ` will be called 42 times.

### Arithmetic #

You can implement all the functionality you saw in the article on Church-encoded natural numbers. You can start gently by converting a Peano number into a normal C# `int`:

```public static int Count(this INaturalNumber n)
{
return n.Cata(0, x => 1 + x);
}```

You can play with the functionality in C# Interactive to get a feel for how it works:

```> NaturalNumber.Eight.Count()
8
> NaturalNumber.Five.Count()
5```

The `Count` extension method uses `Cata` to count the level of recursion. The `zero` value is, not surprisingly, `0`, and the successor function simply adds one to the previous number. Since the successor function runs as many times as encoded by the Peano number, and since the initial value is `0`, you get the integer value of the number when `Cata` exits.

A useful building block you can write using `Cata` is a function to increment a natural number by one:

```public static INaturalNumber Increment(this INaturalNumber n)
{
return n.Cata(One, p => new Successor(p));
}```

This, again, works as you'd expect:

```> NaturalNumber.Zero.Increment().Count()
1
> NaturalNumber.Eight.Increment().Count()
9```

With the `Increment` method and `Cata`, you can easily implement addition:

```public static INaturalNumber Add(this INaturalNumber x, INaturalNumber y)
{
return x.Cata(y, p => p.Increment());
}```

The trick here is to use `y` as the `zero` case for `x`. In other words, if `x` is zero, then `Add` should return `y`. If `x` isn't zero, then `Increment` it as many times as the number encodes, but starting at `y`. In other words, start with `y` and `Increment` `x` times.

The catamorphism makes it much easier to implement arithmetic operation. Just consider multiplication, which wasn't the simplest implementation in the previous article. Now, it's as simple as this:

```public static INaturalNumber Multiply(this INaturalNumber x, INaturalNumber y)
{
}```

Start at `0` and simply `Add(y)` `x` times.

```> NaturalNumber.Nine.Multiply(NaturalNumber.Four).Count()
36```

Finally, you can also implement some common predicates:

```public static IChurchBoolean IsZero(this INaturalNumber n)
{
return n.Cata<IChurchBoolean>(new ChurchTrue(), _ => new ChurchFalse());
}

public static IChurchBoolean IsEven(this INaturalNumber n)
{
return n.Cata<IChurchBoolean>(new ChurchTrue(), b => new ChurchNot(b));
}

public static IChurchBoolean IsOdd(this INaturalNumber n)
{
return new ChurchNot(n.IsEven());
}```

Particularly `IsEven` is elegant: It considers `zero` even, so simply uses a `new ChurchTrue()` object for that case. In all other cases, it alternates between false and true by negating the predecessor.

```> NaturalNumber.Three.IsEven().ToBool()
false```

It seems convincing that we can use `Cata` to implement all the other functionality we need. That seems to be a characteristic of a catamorphism. Still, how do we know that `Cata` is, in fact, the catamorphism for natural numbers?

### Peano F-Algebra #

As in the previous article, I'll use `Fix` and `cata` as explained in Bartosz Milewski's excellent article on F-Algebras. The `NatF` type comes from his article as well:

```data NatF a = ZeroF | SuccF a deriving (Show, Eq, Read)

instance Functor NatF where
fmap _ ZeroF = ZeroF
fmap f (SuccF x) = SuccF \$ f x```

You can use the fixed point of this functor to define numbers with a shared type. Here's just the first ten:

```zeroF, oneF, twoF, threeF, fourF, fiveF, sixF, sevenF, eightF, nineF :: Fix NatF
zeroF  = Fix ZeroF
oneF   = Fix \$ SuccF zeroF
twoF   = Fix \$ SuccF oneF
threeF = Fix \$ SuccF twoF
fourF  = Fix \$ SuccF threeF
fiveF  = Fix \$ SuccF fourF
sixF   = Fix \$ SuccF fiveF
sevenF = Fix \$ SuccF sixF
eightF = Fix \$ SuccF sevenF
nineF  = Fix \$ SuccF eightF```

That's all you need to identify the catamorphism.

At this point, you have two out of three elements of an F-Algebra. You have an endofunctor (`NatF`), and an object `a`, but you still need to find a morphism `NatF a -> a`.

As in the previous article, start by writing a function that will become the catamorphism, based on `cata`:

```natF = cata alg
where alg ZeroF = undefined
alg (SuccF predecessor) = undefined```

While this compiles, with its `undefined` implementations, it obviously doesn't do anything useful. I find, however, that it helps me think. How can you return a value of the type `a` from the `ZeroF` case? You could pass an argument to the `natF` function:

```natF z = cata alg
where alg ZeroF = z
alg (SuccF predecessor) = undefined```

In the `SuccF` case, `predecessor` is already of the polymorphic type `a`, so instead of returning a constant value, you can supply a function as an argument to `natF` and use it in that case:

```natF :: a -> (a -> a) -> Fix NatF -> a
natF z next = cata alg
where alg ZeroF = z
alg (SuccF predecessor) = next predecessor```

This works. Since `cata` has the type `Functor f => (f a -> a) -> Fix f -> a`, that means that `alg` has the type `f a -> a`. In the case of `NatF`, the compiler infers that the `alg` function has the type `NatF a -> a`, which is just what you need!

For good measure, I should point out that, as usual, the above `natF` function isn't the only possible catamorphism. Trivially, you can flip the order of the arguments, and this would also be a catamorphism. These two alternatives are isomorphic.

The `natF` function identifies the Peano number catamorphism, which is equivalent to the C# representation in the beginning of the article. I called the function `natF`, because there's a tendency in Haskell to name the 'case analysis' or catamorphism after the type, just with a lower-case initial letter.

### Basis #

A catamorphism can be used to implement most (if not all) other useful functionality, like all of the above C# functionality. In fact, I wrote the Haskell code first, and then translated my implementations into the above C# extension methods. This means that the following functions apply the same reasoning:

```evenF :: Fix NatF -> Fix BoolF
evenF = natF trueF notF

oddF :: Fix NatF -> Fix BoolF
oddF = notF . evenF

incF :: Fix NatF -> Fix NatF
incF = natF oneF \$ Fix . SuccF

addF :: Fix NatF -> Fix NatF -> Fix NatF
addF x y = natF y incF x

multiplyF :: Fix NatF -> Fix NatF -> Fix NatF
multiplyF x y = natF zeroF (addF y) x```

Here are some GHCi usage examples:

```Prelude Boolean Nat> evenF eightF
Fix TrueF
Prelude Boolean Nat> toNum \$ multiplyF sevenF sixF
42```

The `toNum` function corresponds to the above `Count` C# method. It is, again, based on `cata`. You can use `ana` to convert the other way:

```toNum :: Num a => Fix NatF -> a
toNum = natF 0 (+ 1)

fromNum :: (Eq a, Num a) => a -> Fix NatF
fromNum = ana coalg
where coalg 0 = ZeroF
coalg x = SuccF \$ x - 1```

This demonstrates that `Fix NatF` is isomorphic to `Num` instances, such as `Integer`.

### Summary #

The catamorphism for Peano numbers is a pair consisting of a zero value and a successor function. The most common description of catamorphisms that I've found emphasise how a catamorphism is like a fold; an operation you can use to reduce a data structure like a list or a tree to a single value. This is what happens here, but even so, the `Fix NatF` type isn't a `Foldable` instance. The reason is that while `NatF` is a polymorphic type, its fixed point `Fix NatF` isn't. Haskell's `Foldable` type class requires foldable containers to be polymorphic (what C# programmers would call 'generic').

When I first ran into the concept of a catamorphism, it was invariably described as a 'generalisation of fold'. The examples shown were always how the catamorphism for linked list is the same as its fold. I found such explanations unhelpful, because I couldn't understand how those two concepts differ.

The purpose with this article series is to show just how much more general the abstraction of a catamorphism is. In this article you saw how an infinitely recursive data structure like Peano numbers have a catamorphism, even though it isn't a parametrically polymorphic type. In the next article, though, you'll see the first example of a polymorphic type where the catamorphism coincides with the fold.

Next: Maybe catamorphism.

### Wish to comment?

You can add a comment to this post by sending me a pull request. Alternatively, you can discuss this post on Twitter or somewhere else with a permalink. Ping me with the link, and I may respond.

#### Published

Monday, 13 May 2019 05:10:00 UTC

#### Tags

"Our team wholeheartedly endorses Mark. His expert service provides tremendous value."
Hire me!
Published: Monday, 13 May 2019 05:10:00 UTC