问题描述
我最近了解了 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 fix
ed 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
有效地将函数本身作为第一个参数传递.但是,通过保持递归为开放状态,我们可以修改要回传"的函数.使用此属性的最佳示例是使用memoize软件包中的noreferrer> memoFix
.
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:修复或不修复的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!