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.WordwordListToInteger :: [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.WordasFix :: [a] -> Fix (ListF a)
asFix = cata FixwordListToInteger :: [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.