为什么GHC作出修正，从而混淆？(Why does GHC make fix so confound

纵观GHC源代码，我可以看到， 修复的定义是：

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

在一个示例中修复程序中使用这样的：

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

这基本上产生由一个增加到无限数字序列。 为了做到这一点修复必须讨好它接收右后卫到非常的功能，因为它是第一个参数的函数。 这是我不清楚如何上面列出修复的定义可以这样做。

这个定义是我才明白修复的工作原理：

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 ？ 它定义为fx ，所以fix f = fx 。 但是，什么是x在这里？ 这是fx ，就像以前一样。 所以，你得到fix f = fx = f (fx) 推理这样你的应用程序的无限链f ： fix f = f (f (f (f ...)))

现在，用(\fx -> 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 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 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应用程序实际上保留：

其结果是，第二个方案需要对列表中的每个元素做分配（但由于该表立即被消耗，该方案仍然有效地固定空间中运行）：

$ ./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绑定。 哈斯克尔什么叫“让”，其他一些语言称之为“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]

见一个温柔的介绍Haskell的部分3.3和3.4的详细阐述对Haskell的懒惰。

在GHC的thunk

来执行计算一个承诺：在GHC，一个尚未-未计算的表达在一个“咚”包裹起来。 当他们绝对必须的thunk，只能判断。 假设我们要fix someFunction 。 根据定义fix ，这是

let x = someFunction x in x

现在，GHC看到的是这样的事情。

let x = MAKE A THUNK in x

因此，它高兴地让一个thunk为你，直到你需要知道什么权一起移动x实际上是。

样张评测

这形实转换的表情正好是指本身。 让我们的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票＃5205 ，对于定义了类似的问题forever 。 这就是为什么我提到的thunk：因为let x = fx in x只分配一个形实转换：在x形实转换。

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 ...)))) 但是，第一个定义使用显式命名; 哈斯克尔（如在大多数其他语言）共享通过命名事物的能力启用：一个名字或多或少保证指的是一个“实体”（在这里， x ）。 所述第二定义不保证任何共享-呼叫的结果fix2 f被代入表达式，所以它也可能被取代为一个值。

但是，一个给定的编译器可以在理论上是聪明一点，并在第二种情况下使用共享为好。

在相关的问题是“Y组合”。 在无类型演算那里没有命名构建体（并且因此无自引用）中，Y组合子通过安排要复制的定义，因此参照自我复制成为可能模仿的自参考。 但在使用环境模型，允许在一个语言命名实体的实现，通过名称直接引用成为可能。

看到两个定义之间的更激烈的差异，比较

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

也可以看看：

• 在流程，你如何使用lambda来创建一个递归函数？
• 在“小策士” Y组合讨论
• 可以折叠来创造无限的名单？

（尤其是尝试在最后一个环节制定出上面两个定义）。

---

从定义工作，为你的榜样fix (\gx -> 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实际创建。 （在上文中，我们写....x.... where {x = ...}用于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:

我也许是来自一个有点简单化的解释内联优化。 如果我们有

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'   

文章来源: Why does GHC make fix so confounding?