为什么 GHC 使修复变得如此令人困惑？

查看 GHC 源代码我可以看到定义fix is:

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

在一个例子中fix像这样使用：

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

这基本上会产生一系列加一到无穷大的数字。为了让这件事发生fix必须将它接收到的函数柯里化回该函数作为它的第一个参数。我不清楚如何定义fix上面列出的可以做到这一点。

这个定义就是我如何理解的fix works:

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

所以现在我有两个问题：

1. 如何x曾经意味着fix x在第一个定义中？
2. 使用第一个定义比使用第二个定义有什么优势吗？

通过应用等式推理，很容易看出这个定义是如何运作的。

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

什么会x当我们尝试评估时评估fix f？它定义为f x, so 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') for f you get

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

Edit：关于你的第二个问题，@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应用程序实际上被保留：

结果是第二个程序需要为列表中的每个元素进行分配（但由于列表立即被消耗，程序仍然有效地在恒定空间中运行）：

$ ./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)
[...]