爲什麼GHC讓修復變得混亂？

Question

綜觀GHC源代碼我可以看到，對於修復的定義是：

fix :: (a -> a) -> a 
fix f = let x = f x in x 

在一個示例修復使用這樣的：

fix (\f x -> let x' = x+1 in x:f x') 

這基本上產生一個序列數量增加1到無限。爲此，修復程序必須將其收到的功能作爲第一個參數進行修改。我不清楚上面列出的修訂號的定義是如何做到的。

這個定義我怎麼來理解如何修復作品：

fix :: (a -> a) -> a 
fix f = f (fix f) 

所以現在我有兩個問題：

1. 如何X真的來臨意味着修復X在第一個定義？
2. 使用第二個定義有什麼好處？

Answer 1

通過應用等式推理很容易看出這個定義是如何工作的。

fix :: (a -> a) -> a 
fix f = let x = f x in x 

會有什麼x評估，當我們試圖評估fix f？它定義爲f x，所以fix f = f x。但是這裏是x？它和以前一樣是f x。所以你得到fix f = f x = f (f x)。通過這種方式推理，您將獲得無限的f應用鏈：fix f = f (f (f (f ...)))。

現在，代(\f x -> let x' = x+1 in x:f x')爲f你

fix (\f x -> let x' = x+1 in x:f x') 
    = (\f x -> let x' = x+1 in x:f x') (f ...) 
    = (\x -> let x' = x+1 in x:((f ...) x')) 
    = (\x -> x:((f ...) x + 1)) 
    = (\x -> x:((\x -> let x' = x+1 in x:(f ...) x') x + 1)) 
    = (\x -> x:((\x -> x:(f ...) x + 1) x + 1)) 
    = (\x -> x:(x + 1):((f ...) x + 1)) 
    = ... 

編輯：關於你提到的第二個問題，@ is7s指出，在評論認爲，第一個定義是可取的，因爲它是更有效的。

要找出原因，讓我們來看看核心爲fix1 (:1) !! 10^8：

a_r1Ko :: Type.Integer  
a_r1Ko = __integer 1 

main_x :: [Type.Integer] 
main_x = 
    : @ Type.Integer a_r1Ko main_x 

main3 :: Type.Integer 
main3 = 
    !!_sub @ Type.Integer main_x 100000000 

正如你所看到的，在轉換之後fix1 (1:)基本上成了main_x = 1 : main_x。注意這個定義是如何引用的 - 這就是「綁結」的意思。這種自我參照表示爲在運行一個簡單的間接指針：

現在讓我們來看看fix2 (1:) !! 100000000：

main6 :: Type.Integer 
main6 = __integer 1 

main5 
    :: [Type.Integer] -> [Type.Integer] 
main5 = : @ Type.Integer main6 

main4 :: [Type.Integer] 
main4 = fix2 @ [Type.Integer] main5 

main3 :: Type.Integer 
main3 = 
    !!_sub @ Type.Integer main4 100000000 

這裏fix2應用程序實際上保留：

結果是，第二個編RAM需要爲列表中的每個元素做分配（但由於該表立即被消耗，該方案仍然有效地固定空間中運行）：

$ ./Test2 +RTS -s 
    2,400,047,200 bytes allocated in the heap 
     133,012 bytes copied during GC 
      27,040 bytes maximum residency (1 sample(s)) 
      17,688 bytes maximum slop 
       1 MB total memory in use (0 MB lost due to fragmentation) 
[...] 

與此相比，第一程序的行爲：

$ ./Test1 +RTS -s   
      47,168 bytes allocated in the heap 
      1,756 bytes copied during GC 
      42,632 bytes maximum residency (1 sample(s)) 
      18,808 bytes maximum slop 
       1 MB total memory in use (0 MB lost due to fragmentation) 
[...] 

Answer 2

x如何在第一個定義中定義x？

fix f = let x = f x in x 

我們在Haskell綁定是遞歸

首先，認識到哈斯克爾允許遞歸let綁定。 Haskell稱之爲「let」，其他一些語言稱爲「letrec」。這對於函數定義來說非常正常。例如：

ghci> let fac n = if n == 0 then 1 else n * fac (n - 1) in fac 5 
120 

但是這對價值定義看起來很奇怪。不過，由於Haskell的非嚴格性，值可以遞歸定義。

ghci> take 5 (let ones = 1 : ones in ones) 
[1,1,1,1,1] 

請參閱A gentle introduction to Haskell第3.3節和第3.4節，瞭解關於Haskell懶惰的更多細節。來執行計算一個承諾：

的thunk在GHC

在GHC，一個尚未-未計算的表達在一個「咚」包裹起來。只有當它們絕對必須是時才評估Thunk。假設我們想要fix someFunction。據fix的定義，這是

let x = someFunction x in x 

現在，GHC看到的是這樣的事情。

let x = MAKE A THUNK in x 

所以高高興興地做一個thunk爲你，直到你需要知道什麼x實際上是對一起移動。

樣張評測

那的thunk的表情正好是指本身。我們以ones爲例，並重寫它以使用fix。

ghci> take 5 (let ones recur = 1 : recur in fix ones) 
[1,1,1,1,1] 

那麼這個thunk會是什麼樣子呢？
我們可以將ones作爲匿名函數\recur -> 1 : recur進行更清晰的演示。

take 5 (fix (\recur -> 1 : recur)) 

-- expand definition of fix 
take 5 (let x = (\recur -> 1 : recur) x in x) 

現在那麼，什麼是x？那麼，即使我們不能肯定什麼x是，我們仍然可以去通過與功能應用：

take 5 (let x = 1 : x in x) 

嗨，瞧，我們回來了，在我們以前的定義。

take 5 (let ones = 1 : ones in ones) 

因此，如果你相信你瞭解如何是一個作品，那麼你有多麼fix工作的一個良好的手感。

---

是否有任何優勢，使用的第一個定義在第二？

是的。問題在於第二個版本可能會導致空間泄漏，即使進行了優化。請參閱GHC trac ticket #5205，對於forever的定義有類似的問題。這就是我提到thunk的原因：因爲let x = f x in x只分配一個thunk：x thunk。

Answer 3

區別在於共享vs複製。

fix1 f = x where x = f x -- more visually apparent way to write the same thing 

fix2 f = f (fix2 f) 

如果我們替換定義成本身，兩者都減少，因爲相同的無限應用鏈f (f (f (f (f ...))))。但第一個定義使用明確的命名;在Haskell中（與大多數其他語言一樣），通過命名事物的能力實現共享：一個名稱或多或少地保證引用一個「實體」（這裏是x）。第二個定義不保證任何共享 - 調用fix2 f的結果被替換爲表達式，因此它也可以被替換爲值。

但是，給定的編譯器在理論上可以很聰明，也可以在第二種情況下使用共享。

相關問題是「Y combinator」。在無類型演算那裏沒有命名構建體（並且因此沒有自引用），ÿ組合子通過佈置爲定義模擬自引用被複制，所以參照拷貝自變得可能。但是在使用環境模型來允許語言中的命名實體的實現中，可以通過名稱直接引用。

要查看這兩個定義之間的更激烈的差異，比較

fibs1 = fix1 ((0:) . (1:) . g) where g (a:t@(b:_)) = (a+b):g t 
fibs2 = fix2 ((0:) . (1:) . g) where g (a:t@(b:_)) = (a+b):g t 

參見：

• In Scheme, how do you use lambda to create a recursive function?
• Y combinator discussion in "The Little Schemer"
• Can fold be used to create infinite lists?

（特別是試着找出上面最後一個鏈接中的最後兩個定義）。

---

從定義工作，爲你的榜樣fix (\g x -> let x2 = x+1 in x : g x2)我們得到

fix1 (\g x -> let x2 = x+1 in x : g x2) 
= fix1 (\g x -> x : g (x+1)) 
= fix1 f where {f = \g x -> x : g (x+1)} 
= fix1 f where {f g x = x : g (x+1)} 
= x  where {x = f x ; f g x = x : g (x+1)} 
= g  where {g = f g ; f g x = x : g (x+1)} -- both g in {g = f g} are the same g 
= g  where {g = \x -> x : g (x+1)}   -- and so, here as well 
= g  where {g x = x : g (x+1)} 

從而爲g正確的遞歸定義實際上是創建。 （在上面，我們寫爲let {x = ...} in ....x....，易讀性）。

但第二推導與代以值回，而不是一個名稱的關鍵的區別進行，如

fix2 (\g x -> x : g (x+1)) 
= fix2 f    where {f g x = x : g (x+1)} 
= f (fix2 f)   where {f g x = x : g (x+1)} 
= (\x-> x : g (x+1)) where {g = fix2 f ; f g x = x : g (x+1)} 
= h     where {h x = x : g (x+1) ; g = fix2 f ; f g x = x : g (x+1)} 

所以實際呼叫將進行如下例如

take 3 $ fix2 (\g x -> x : g (x+1)) 10 
= take 3 (h 10)  where {h x = x : g (x+1) ; g = fix2 f ; f g x = x : g (x+1)} 
= take 3 (x:g (x+1)) where {x = 10 ;    g = fix2 f ; f g x = x : g (x+1)} 
= x:take 2 (g x2) where {x2 = x+1 ; x = 10 ; g = fix2 f ; f g x = x : g (x+1)} 
= x:take 2 (g x2) where {x2 = x+1 ; x = 10 ; g = f (fix2 f) ; f g x = x : g (x+1)} 
= x:take 2 (x2 : g2 (x2+1)) where {    g2 = fix2 f ; 
          x2 = x+1 ; x = 10 ;     f g x = x : g (x+1)} 
= ...... 

，我們看到一個新的結合（爲g2）在這裏建立，而不是以前的一個（g）被重用爲與fix1定義。

Answer 4

我也許有一個簡單的解釋來自inlining優化。如果我們有

fix :: (a -> a) -> a 
fix f = f (fix f) 

然後fix是一個遞歸函數，這意味着它不能在使用它的地方被內聯（一INLINE編譯將被忽略，如果給定的）。

然而

fix' f = let x = f x in x 

是不遞歸函數 - 它永遠不會調用自身。裏面只有x遞歸。因此調用

fix' (\r x -> let x' = x+1 in x:r x') 

當編譯器可以使用標準的內聯成

(\f -> (let y = f y in y)) (\r x -> let x' = x+1 in x:r x') 

然後繼續簡化它，例如

let y = (\r x -> let x' = x+1 in x:r x') y in y 
let y = (\ x -> let x' = x+1 in x:y x') in y 

這就像函數中定義沒有fix遞歸符號：

y  x = let x' = x+1 in x:y x'