Can one express catamorphism through Data.Function.fix?

Question

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.

Pacify

I don't understand. What happens if you try the analogous fixcata f = fix $ \g -> f . fmap g . unFix ? – Lupulin

@Lupulin Oh. Defeated again. I'm poor with fixpoints. I should probably delete this question to avoid embarrassment. – Pacify

SO is not a game when one gets "defeated" :) There's nothing wrong in asking a question without knowing the answer beforehand -- indeed that's the whole point of asking! – Lupulin

Answer 1

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.

Lupulin

Thank you! Can you also take a look at the updated post? – Pacify

@Kindaro you should make that update (which I rolled back for now) a separate question, since it doesn't directly relate to the original question's title. – Seraphic

@Kindaro Also see this first. I think it's exactly the same issue which improves performance. – Lupulin