blog

You may have seen my post on co-(Elgot algebras), in which I mentioned I had been using some exotic recursion schemes for my gmpint package. I came across a similar example, this time for Mendler-style recursion schemes. To my knowledge, it is the only published example of a Mendler-style catamorphism.

The problem is the inverse of the last problem: given the of limbs (here Word64s), we wish to return Haskell's Integer type. With a vanilla catamorphism we can write the following:

import Data.Functor.Foldable
import Data.Word
wordListToInteger :: [Word64] -> Integer
wordListToInteger = cata a where
    a Nil         = 0
    a (Cons x xs) = fromIntegral x + base * xs

We can write this as a Mendler-style catamorphism as follows:

import Data.Functor.Foldable
import Data.Word
asFix :: [a] -> Fix (ListF a)
asFix = cata Fix
wordListToInteger :: [Word64] -> Integer
wordListToInteger = mcata ma . asFix where
    ma f (Cons x xs) = fromIntegral x + base * f xs
    ma _ Nil         = 0

This implementation is slightly slower than a simple catamorphism, so it was not published to Hackage, but hopefully it is instructive.