haskell - 可以通过 Data.Function.fix 表达变态吗？

Question

我在fixana这里有这个可爱的功能，它的执行速度比她姐姐快 5 倍ana。（我有一份criterion报告支持我）

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

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

我可以cata用同样的方式表达他们的表弟吗？

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

在我看来，我做不到，但过去我曾多次被我的 SO 伙伴羞辱过。

Answer 1

实际上，这与变质无关。

每当一个函数被定义为

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

可以使用fixas重写它

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

在发布的代码中，我们有一个轻微的变体

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

我们可以认为上面f是递归定义的。但是，如果我们认为f x（而不是f）被递归定义，它会更简单。

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

这应该比简单的翻译更有效率

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

因为我们不需要g用相同的参数一遍又一遍地调用x。