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.