Haskell中fix函数两种定义的结构共享差异解析

两种fix函数的实现 #

• 带结构共享的版本：

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

• 不带结构共享的版本：

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

结构共享差异的核心原因 #

以阶乘函数fact n = if n == 0 then 1 else n * fact (n-1)为例：

• 不带结构共享的版本，展开过程会不断生成全新的递归调用：

  fix fact 5
  = fact (fix fact) 5
  = 5 * (fix fact) 4
  = 5 * (fact (fix fact) 4)
  = 5 * 4 * (fix fact) 3
  ...
  

  每一步的fix fact都是独立的函数调用，每次递归都会重新展开成fact (fix fact)，没有复用任何已有的计算分支，自然不存在结构共享。

• 带结构共享的版本，通过let绑定创建了一个自引用的惰性值（thunk）：

  fix fact = let x = fact x in x
  

  当调用x 5时，所有递归环节里的x都是同一个绑定的thunk——比如计算x 5会触发fact x 5，而fact里的x (n-1)直接指向最初绑定的那个x，不会重新生成新的fix fact实例。所有递归调用复用同一个值，这就是结构共享的本质。

展开最后一步的性质 #

带结构共享的展开最后一步不是多步融合操作，而是惰性求值下的共享thunk绑定。let x = f x in x只是创建了一个可复用的自引用惰性值，当x被求值时，f里的递归引用直接指向这个已存在的thunk，整个过程没有多步的“融合”动作，只是通过绑定实现了引用共享，避免了重复展开和计算。

内容的提问来源于stack exchange，提问作者roi_saumon