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.
