# Can one express catamorphism through Data.Function.fix?

I have this lovely `fixana` function here that performs about 5 times faster than her sister `ana`. (i have a `criterion` report to back me on this)

``````ana alg = Fix . fmap (ana alg) . alg

fixana alg = fix \$ \f -> Fix . fmap f . alg
``````

Can I express their cousin `cata` in the same fashion?

``````cata f = f . fmap (cata f) . unFix
``````

It seems to me that I cannot, but I have been humbled by my S.O. fellows quite a few times in the past.

Solution

• Actually, this has nothing to do with catamorphisms.

Whenever a function is defined as

``````f = (... f ...)   -- some expression involving f
``````

one can rewrite it using `fix` as

``````f = fix \$ \g -> (... g ...)
``````

In the posted code we have a slight variant

``````f x = (... (f x) ...)
``````

We can regard the above as `f` being defined recursively. However, it's simpler if we regard `f x` (rather than `f`) being defined recursively.

``````f x = fix \$ \g -> (... g ...)
``````

This should be more efficient than the plain translation

``````f = fix \$ \g x -> (... (g x) ...)
``````

since we don't need to call `g` over and over again with the same argument `x`.