在 Python 中，我可以寫
fac = lambda slf, n: 1 if n == 0 else n * slf(slf, n - 1)
print(fac(fac, 4)) # prints 24
我正在嘗試在 Haskell 中復制它。但是，Haskell 不會讓我這樣做：
fac _ 0 = 1
fac slf n = n * slf slf (n - 1)
我收到此錯誤：
? Occurs check: cannot construct the infinite type: t ~ t -> p -> p
? In the first argument of ‘slf’, namely ‘slf’
In the second argument of ‘(*)’, namely ‘slf slf (n - 1)’
In the expression: n * slf slf (n - 1)
? Relevant bindings include
n :: p (bound at app/Main.hs:9:10)
slf :: t -> p -> p (bound at app/Main.hs:9:6)
fac_ :: (t -> p -> p) -> p -> p (bound at app/Main.hs:8:1)
|
9 | fac_ slf n = n * slf slf (n - 1)
| ^^^
似乎問題是我無法傳遞slf給slf. 有沒有辦法解決這個問題？謝謝你。
uj5u.com熱心網友回復：
您不能直接執行此操作。Haskell 中每個術語的型別都必須能夠寫下來，如果寫下來，您提議的術語的型別將是無限長的。錯誤訊息說了這么多：它說“我想寫這個型別，但它包含自己，所以我在炸毀你的RAM之前停止嘗試”。
然而，Haskell 確實有遞回型別。我們每天都以串列、樹和任何其他自相似結構的形式使用它們。Haskell 永遠不會允許你寫一個型別Either () (Int, t)， where tis Either () (Int, t)。但是，這究竟是什么[Int]是; 它只是隱藏在資料建構式后面，因此型別的值[Int]可以無限長且自相似（串列的尾部看起來像串列），但型別仍然以漂亮、整潔、有限的形式撰寫[Int]。我們可以使用完全相同的技巧來獲得一個可以應用于自身的函式。
newtype Mu a b = Mu { unMu :: Mu a b -> a -> b }
該型別Mu a b被定義為包含一個接受 aMu a b和 ana并產生 a的函式b。我們現在可以撰寫一個fac將 aMu a a作為引數的函式。
fac :: (Num a, Eq a) => Mu a a -> a -> a
fac _ 0 = 1
fac slf n = n * unMu slf slf (n - 1)
并將其稱為
fac (Mu fac) 5
所以我們永遠不能把fac它作為一個引數傳遞給它自己。這將始終產生發生檢查[1]。但是我們可以將Mu fac，它具有很好的簡單型別Mu a a，作為引數傳遞給fac，這是一個普通的函式。一層間接，你就有了你的遞回組合器。
您可以使用相同的Mu技巧來撰寫完整的、非遞回的Y 組合器。這本身就是一項有價值的練習，我強烈推薦。
[1] 它將始終對函式型別進行發生檢查。您可能可以使用多型遞回做一些真正瘋狂的事情，以創建一個可以接受自身（的多型變體）作為引數的函式，使用類似于printf在 Haskell 中獲取可變引數的技巧。這留給讀者作為練習。
uj5u.com熱心網友回復：
您不能在 Haskell 中執行此操作，原因 Silvio Mayolo 已解釋過。但是，就像在 Python 中一樣，您不需要這樣做，因為您可以為函式命名并讓它直接呼叫自身：
fac 0 = 1
fac n = n * fac (n - 1)
就像在 Python 中一樣，這不必是頂級函式：您可以在let系結中定義此函式并像使用任何 lambda 一樣使用它。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/389039.html
標籤：哈斯克尔