是否可以通过 Data.Function.fix 来表达变形？

Question

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

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

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

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

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

在我看来我不能，但我对我的 S.O 感到谦卑。老乡们过去好几次了

Answer 1

实际上，这与变形无关。

每当函数定义为

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

可以使用 fix 重写为

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。