Haskell:修复或不修复 [英] Haskell: to fix or not to fix

问题描述

我最近了解了 Data.Function.fix ，现在我想将其应用于所有地方.例如，每当我看到递归函数时，我都想"fix"它.所以基本上我的问题是我应该在何时何地使用它.

I recently learned about Data.Function.fix, and now I want to apply it everywhere. For example, whenever I see a recursive function I want to "fix" it. So basically my question is where and when should I use it.

使其更具针对性:

1)假设我有以下代码用于n的因式分解:

1) Suppose I have the following code for factorization of n:

f n = f' n primes
  where
    f' n (p:ps) = ...
    -- if p^2<=n: returns (p,k):f' (n `div` p^k) ps for k = maximum power of p in n
    -- if n<=1: returns []
    -- otherwise: returns [(n,1)]

如果我用fix重写它，我会有所收获吗?丢东西了吗?是否有可能通过将显式递归重写为fix -version而解决，反之亦然，则会导致堆栈溢出?

If I rewrite it in terms of fix, will I gain something? Lose something? Is it possible, that by rewriting an explicit recursion into fix-version I will resolve or vice versa create a stack overflow?

2)处理列表时，有几种解决方案:递归/修复，foldr/foldl/foldl'，可能还有其他解决方案.是否有关于何时使用的一般指导/建议?例如，您是否会在无限质数列表上使用foldr重写上述代码?

2) When dealing with lists, there are several solutions: recursion/fix, foldr/foldl/foldl', and probably something else. Is there any general guide/advice on when to use each? For example, would you rewrite the above code using foldr over the infinite list of primes?

可能还有其他一些重要的问题，此处未涉及.也欢迎与fix的用法有关的任何其他注释.

There are, probably, other important questions not covered here. Any additional comments related to the usage of fix are welcome as well.

推荐答案

以明确的fix形式编写可以得到的一件事是，将递归保持为打开"状态.

One thing that can be gained by writing in an explicitly fixed form is that the recursion is left "open".

factOpen :: (Integer -> Integer) -> Integer -> Integer
factOpen recur 0 = 1
factOpen recur n = n * recur (pred n)

我们可以使用fix找回常规fact

We can use fix to get regular fact back

fact :: Integer -> Integer
fact = fix factOpen

之所以起作用，是因为fix有效地将函数本身作为第一个参数传递.但是，通过保持递归为开放状态，我们可以修改要回传"的函数.使用此属性的最佳示例是使用

This works because fix effectively passes a function itself as its first argument. By leaving the recursion open, however, we can modify which function gets "passed back". The best example of using this property is to use something like memoFix from the memoize package.

factM :: Integer -> Integer
factM = memoFix factOpen

现在factM具有内置的备忘录.

And now factM has built-in memoization.

实际上，我们拥有开放式递归，这要求我们将递归位归为一阶事物.递归绑定是Haskell允许在语言级别进行递归的一种方法，但是我们可以构建其他更专业的形式.

Effectively, we have that open-style recursion requires us impute the recursive bit as a first-order thing. Recursive bindings are one way that Haskell allows for recursion at the language level, but we can build other, more specialized forms.

这篇关于Haskell:修复或不修复的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！