Haskell 是否修复结构共享

Question

在这个wiki关于在haskell中使用fix函数进行递归时，他们定义了两种定义fix的方法。 结构共享的一个：

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

没有结构共享的一个：

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

现在我真的不明白为什么第一个是结构共享而另一个不是。我一直盯着阶乘函数的展开式，但我无法理解在哪里看到一个具有结构共享而另一个没有。

结构分享：

 fix fact'
= let rec = fact' rec in rec
= let rec = (\rec' n -> if n == 0 then 1 else n * rec' (n-1)) rec in rec
= let rec = (\n -> if n == 0 then 1 else n * rec (n-1)) in rec
= let rec = (\n -> if n == 0 then 1 else n * rec (n-1)) in 
   \n -> if n == 0 then 1 else n * rec (n-1)
= let rec = (\n -> if n == 0 then 1 else n * rec (n-1)) in 
   \n -> if n == 0 then 1
        else n * (if n-1 == 0 then 1 else (n-1) * rec (n-2))
= ...

（对于这个，我不太明白最后一步，是多个步骤的融合吗？）

无结构共享：

 fix fact'
= let rec = fact' rec in rec
= let rec = (\rec' n -> if n == 0 then 1 else n * rec' (n-1)) rec in rec
= let rec = (\n -> if n == 0 then 1 else n * rec (n-1)) in rec
= let rec = (\n -> if n == 0 then 1 else n * rec (n-1)) in 
   \n -> if n == 0 then 1 else n * rec (n-1)
= let rec = (\n -> if n == 0 then 1 else n * rec (n-1)) in 
   \n -> if n == 0 then 1
        else n * (if n-1 == 0 then 1 else (n-1) * rec (n-2))
= ...

Answer 1

区别在于递归的真正位置。在第一种情况下，

fix

创建了一个递归对象

x

，但

fix

本身不是递归的。 结果是。相反，在后一种情况下，

fix

是独立于

f

递归的。因此没有机会进行结构共享，因为没有可以共享的引用（除了

fix

函数指针）。

正如评论中所建议的，一个更好的例子是

fix (1:)

。第一个变体扩展到预期的

let x = 1:x in x

，其中引用

x

与底层对象共享（使用

1:2:x

可能会更明显）。它的扩展看起来或多或少像

• x

  （替代

  x := 1:x

  ）

• 1:x

  （替代

  x := 1:x

  ）

• 1:1:x

  （替代

  x := 1:x

  ）

• 1:1:1:x

  ...

在第二种情况下，你最终会得到

1 : fix (1:)

。

fix (1:)

部分是对函数的调用，编译器显然不清楚它将计算出与整个表达式完全相同的结果。它也还不是一个真正的值。因此，即使简化为 ANF 为 let x = fix (1:) in 1 : x

，也没有直接迹象表明这里的任何两个事物是相同的并且可以在内存中共享一个位置。评估还会暴露另一个差异：

• fix (1:)

  （减少）

• 1 : fix (1:)

  （减少）

• 1 : 1 : fix (1:)

  （减少）

• 1 : 1 : 1 : fix (1:)

  ...

如图所示，不同之处在于，在第一种情况下我们使用替代，而在第二种情况下我们使用减少。替换涉及引用，这正是共享的精神，而减少则不然。

---

（所有这些

可以被优化有时，但这是另一个话题）