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 
     .....