Haskell：修复或不修复

Question

我最近了解到Data.Function.fix，现在我想将它应用到任何地方。例如，每当我看到一个递归函数时，我想要“fix”它。所以基本上我的问题是我应该在何时何地使用它。

为了使它更具体：

1）假设我有一个的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我会解决或反之亦然创建堆栈溢出？

2）当处理列表时，有几种解决方案：递归/修复，foldr/foldl/foldl'，可能还有其他的。有什么时候使用每一个的一般指导/建议？例如，你会重写上面的代码使用foldr在素数的无限列表上吗？

这里可能还有其他重要的问题。任何与使用fix有关的其他意见也是受欢迎的。

Answer 1

通过编写一个明确的fix ed表单可以获得的一件事是递归保持“打开”。

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

我们可以使用fix得到规则fact回

fact :: Integer -> Integer 
fact = fix factOpen 

这工作，因为fix有效地传递一个函数本身作为第一个参数。然而，通过保持递归打开，我们可以修改哪个函数被“传回”。使用这个属性的最好的例子是使用类似memoFix from the memoize package。

factM :: Integer -> Integer 
factM = memoFix factOpen 

而现在factM已内置memoization。

实际上，我们认为开放式递归要求我们将递归位作为一阶事物进行推测。递归绑定是Haskell允许在语言级递归的一种方式，但我们可以构建其他更专用的形式。

Answer 2

1）fix只是一个函数，当你使用一些递归时，它会提高你的代码。它使你的代码更漂亮。例如使用访问：Haskell Wikibook - Fix and recursion。

2）你知道foldr是什么吗？似乎foldr在分解中没有用（或者我不明白你的意思）。 这里是没有修复因式分解：

fact xs = map (\x->takeWhile (\y->y/=[]) x) . map (\x->factIt x) $ xs 
where factIt n = map (\x->getFact x n []) [2..n] 
    getFact i n xs 
    | n `mod` i == 0 = getFact i (div n i) xs++[i] 
    | otherwise  = xs 

与修复（这恰好就像前面）：

fact xs = map (\x->takeWhile (\y->y/=[]) x) . map (\x->getfact x) $ xs 
    where getfact n = map (\x->defact x n) [2..n] 
     defact i n = 
     fix (\rec j k xs->if(mod k j == 0)then (rec j (div k j) xs++[j]) else xs) i n [] 

这是不漂亮，因为在这种情况下，解决办法是不是好选择（但总有人可以写得更好）。

Answer 3

我想提一下fix的另一种用法;假设你有一个由加法，负数和整数文字组成的简单语言。也许你已经写了一个解析器，这需要String和输出Tree：

data Tree = Leaf String | Node String [Tree] 
parse :: String -> Tree 

-- parse "-(1+2)" == Node "Neg" [Node "Add" [Node "Lit" [Leaf "1"], Node "Lit" [Leaf "2"]]] 

现在，你想你的树计算结果为一个整数：

fromTree (Node "Lit" [Leaf n]) = case reads n of {[(x,"")] -> Just x; _ -> Nothing} 
fromTree (Node "Neg" [e])  = liftM negate (fromTree e) 
fromTree (Node "Add" [e1,e2]) = liftM2 (+) (fromTree e1) (fromTree e2) 

其他假设有人决定扩展语言;他们想要增加乘法。他们必须有权访问原始源代码。他们可以尝试以下方法：

fromTree' (Node "Mul" [e1, e2]) = ... 
fromTree' e      = fromTree e 

但随后Mul只能出现一次，在表达的最高水平，因为调用fromTree将不会意识到Node "Mul"案件。 Tree "Neg" [Tree "Mul" a b]将不起作用，因为原来的fromTree没有"Mul"的模式。但是，如果同样的功能使用fix写着：

fromTreeExt :: (Tree -> Maybe Int) -> (Tree -> Maybe Int) 
fromTreeExt self (Node "Neg" [e]) = liftM negate (self e) 
fromTreeExt .... -- other cases 

fromTree = fix fromTreeExt 

然后扩展语言是可能的：

fromTreeExt' self (Node "Mul" [e1, e2]) = ... 
fromTreeExt' self e      = fromTreeExt self e 

fromTree' = fix fromTreeExt' 

现在，扩展fromTree'会正确评价树，因为self在fromTreeExt'指整个功能，包括“Mul”情况。

该方法使用here（上面的例子是本文中用法的紧密适用版本）。

Answer 4

请注意_Y f = f (_Y f)（递归，值 - 复制）和fix f = x where x = f x（corecursion，reference - sharing）之间的差异。

Haskell的let和where绑定是递归的：LHS和RHS上的同名引用同一个实体。参考文献是共享。

在_Y的定义中，不存在共享（除非编译器执行常见子表达式消除的激进优化）。这意味着它描述了递归，其中重复是通过应用拷贝来实现的，如在recursive function creating its own copies的经典隐喻中。另一方面，Corecursion依靠共享来引用同一个实体。

一个例子，由素数

2 : _Y ((3:) . gaps 5 . _U . map (\p-> [p*p, p*p+2*p..])) 

-- gaps 5 == ([5,7..] \\) 
-- _U  == sort . concat 

要么再利用其自身的输出（与fix，let g = ((3:)...) ; ps = g ps in 2 : ps）或创建自身单独的素数供应（与_Y，let g() = ((3:)...) (g()) in 2 : g()）来计算。

参见：

• double stream feed to prevent unneeded memoization?
• How to implement an efficient infinite generator of prime numbers in Python?

---

或者，用阶乘函数通常的例子，

gen rec n = n<2 -> 1 ; n * rec (n-1)   -- "if" notation 

facrec = _Y gen 
facrec 4 = gen (_Y gen) 4 
     = let {rec=_Y gen} in (\n-> ...) 4 
     = let {rec=_Y gen} in (4<2 -> 1 ; 4*rec 3) 
     = 4*_Y gen 3 
     = 4*gen (_Y gen) 3 
     = 4*let {rec2=_Y gen} in (3<2 -> 1 ; 3*rec2 2) 
     = 4*3*_Y gen 2       -- (_Y gen) recalculated 
     ..... 

fac  = fix gen 
fac 4 = (let f = gen f in f) 4    
     = (let f = (let {rec=f} in (\n-> ...)) in f) 4 
     = let {rec=f} in (4<2 -> 1 ; 4*rec 3) -- f binding is created 
     = 4*f 3 
     = 4*let {rec=f} in (3<2 -> 1 ; 3*rec 2) 
     = 4*3*f 2        -- f binding is reused 
     .....