# Payment types catamorphism by Mark Seemann

*You can find the catamorphism for a custom sum type. Here's an example.*

This article is part of an article series about catamorphisms. A catamorphism is a universal abstraction that describes how to digest a data structure into a potentially more compact value.

This article presents the catamorphism for a domain-specific sum type, as well as how to identify it. The beginning of this article presents the catamorphism in C#, with a few examples. The rest of the article describes how to deduce 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.

In all previous articles in the series, you've seen catamorphisms for well-known data structures: Boolean values, Peano numbers, Maybe, trees, and so on. These are all general-purpose data structures, so you might be left with the impression that catamorphisms are only related to such general types. That's not the case. The point of this article is to demonstrate that you can find the catamorphism for your own custom, domain-specific sum type as well.

### C# catamorphism #

The custom type we'll examine in this article is the Church-encoded payment types I've previously written about. It's just an example of a custom data type, but it serves the purpose of illustration because I've already shown it as a Church encoding in C#, as a Visitor in C#, and as a discriminated union in F#.

The catamorphism for the `IPaymentType`

interface is the `Match`

method:

T Match<T>( Func<PaymentService, T> individual, Func<PaymentService, T> parent, Func<ChildPaymentService, T> child);

As has turned out to be a common trait, the catamorphism is identical to the Church encoding.

I'm not going to show more than a few examples of using the `Match`

method, because you can find other examples in the previous articles,

> IPaymentType p = new Individual(new PaymentService("Visa", "Pay")); > p.Match(ps => ps.Name, ps => ps.Name, cps => cps.PaymentService.Name) "Visa" > IPaymentType p = new Parent(new PaymentService("Visa", "Pay")); > p.Match(ps => ps.Name, ps => ps.Name, cps => cps.PaymentService.Name) "Visa" > IPaymentType p = new Child(new ChildPaymentService("1234", new PaymentService("Visa", "Pay"))); > p.Match(ps => ps.Name, ps => ps.Name, cps => cps.PaymentService.Name) "Visa"

These three examples from a *C# Interactive* session demonstrate that no matter which payment method you use, you can use the same `Match`

method call to extract the payment name from the `p`

object.

### Payment types F-Algebra #

As in the previous article, I'll use `Fix`

and `cata`

as explained in Bartosz Milewski's excellent article on F-Algebras.

First, you'll have to define the auxiliary types involved in this API:

data PaymentService = PaymentService { paymentServiceName :: String , paymentServiceAction :: String } deriving (Show, Eq, Read) data ChildPaymentService = ChildPaymentService { originalTransactionKey :: String , parentPaymentService :: PaymentService } deriving (Show, Eq, Read)

While F-Algebras and fixed points are mostly used for recursive data structures, you can also define an F-Algebra for a non-recursive data structure. You already saw examples of that in the articles about Boolean catamorphism, Maybe catamorphism, and Either catamorphism. While each of the three payment types have associated data, none of it is parametrically polymorphic, so a single type argument for the carrier type suffices:

data PaymentTypeF c = IndividualF PaymentService | ParentF PaymentService | ChildF ChildPaymentService deriving (Show, Eq, Read) instance Functor PaymentTypeF where fmap _ (IndividualF ps) = IndividualF ps fmap _ (ParentF ps) = ParentF ps fmap _ (ChildF cps) = ChildF cps

I chose to call the carrier type `c`

(for *carrier*). As was also the case with `BoolF`

, `MaybeF`

, and `EitherF`

, the `Functor`

instance ignores the map function because the carrier type is missing from all three cases. Like the `Functor`

instances for `BoolF`

, `MaybeF`

, and `EitherF`

, it'd seem that nothing happens, but at the type level, this is still a translation from `PaymentTypeF c`

to `PaymentTypeF c1`

. Not much of a function, perhaps, but definitely an *endofunctor*.

Some helper functions make it a little easier to create `Fix PaymentTypeF`

values, but there's really not much to them:

individualF :: PaymentService -> Fix PaymentTypeF individualF = Fix . IndividualF parentF :: PaymentService -> Fix PaymentTypeF parentF = Fix . ParentF childF :: ChildPaymentService -> Fix PaymentTypeF childF = Fix . ChildF

That's all you need to identify the catamorphism.

### Haskell catamorphism #

At this point, you have two out of three elements of an F-Algebra. You have an endofunctor (`PaymentTypeF`

), and an object `c`

, but you still need to find a morphism `PaymentTypeF c -> c`

.

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

:

paymentF = cata alg where alg (IndividualF ps) = undefined alg (ParentF ps) = undefined alg (ChildF cps) = 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 `c`

from the `IndividualF`

case? You could pass an argument to the `paymentF`

function, but you shouldn't ignore the data `ps`

contained in the case, so it has to be a function:

paymentF fi = cata alg where alg (IndividualF ps) = fi ps alg (ParentF ps) = undefined alg (ChildF cps) = undefined

I chose to call the argument `fi`

, for *function, individual*. You can pass a similar argument to deal with the `ParentF`

case:

paymentF fi fp = cata alg where alg (IndividualF ps) = fi ps alg (ParentF ps) = fp ps alg (ChildF cps) = undefined

And of course with the remaining `ChildF`

case as well:

paymentF :: (PaymentService -> c) -> (PaymentService -> c) -> (ChildPaymentService -> c) -> Fix PaymentTypeF -> c paymentF fi fp fc = cata alg where alg (IndividualF ps) = fi ps alg (ParentF ps) = fp ps alg (ChildF cps) = fc cps

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 `PaymentTypeF`

, the compiler infers that the `alg`

function has the type `PaymentTypeF c -> c`

, which is just what you need!

You can now see what the carrier type `c`

is for. It's the type that the algebra extracts, and thus the type that the catamorphism returns.

This, then, is the catamorphism for the payment types. Except for the tree catamorphism, all catamorphisms so far have been pairs, but this one is a triplet of functions. This is because the sum type has three cases instead of two.

As you've seen repeatedly, this isn't the only possible catamorphism, since you can, for example, trivially reorder the arguments to `paymentF`

. The version shown here is, however, equivalent to the above C# `Match`

method.

### Usage #

You can use the catamorphism as a basis for other functionality. If, for example, you want to convert a `Fix PaymentTypeF`

value to JSON, you can first define an Aeson record type for that purpose:

data PaymentJson = PaymentJson { name :: String , action :: String , startRecurrent :: Bool , transactionKey :: Maybe String } deriving (Show, Eq, Generic) instance ToJSON PaymentJson

Subsequently, you can use `paymentF`

to implement a conversion from `Fix PaymentTypeF`

to `PaymentJson`

, as in the previous articles:

toJson :: Fix PaymentTypeF -> PaymentJson toJson = paymentF (\(PaymentService n a) -> PaymentJson n a False Nothing) (\(PaymentService n a) -> PaymentJson n a True Nothing) (\(ChildPaymentService k (PaymentService n a)) -> PaymentJson n a False $ Just k)

Testing it in GHCi, it works as it's supposed to:

Prelude Data.Aeson B Payment> B.putStrLn $ encode $ toJson $ parentF $ PaymentService "Visa" "Pay" {"transactionKey":null,"startRecurrent":true,"action":"Pay","name":"Visa"}

Clearly, it would have been easier to define the payment types shown here as a regular Haskell sum type and just use standard pattern matching, but the purpose of this article isn't to present useful code; the only purpose of the code here is to demonstrate how to identify the catamorphism for a custom domain-specific sum type.

### Summary #

Even custom, domain-specific sum types have catamorphisms. This article presented the catamorphism for a custom payment sum type. Because this particular sum type has three cases, the catamorphism is a triplet, instead of a pair, which has otherwise been the most common shape of catamorphisms in previous articles.