为何Haskell的thunk如此高效？斐波那契线性时间之谜

你的猜想完全正确：Haskell里的惰性求值结合纯函数的不可变性，实现了计算结果的自动缓存（也就是记忆化），避免了重复计算，因此能达到线性时间复杂度。

拆解Haskell的实现逻辑 #

fib = 0 : 1 : zipWith (+) fib (tail fib)

这里的fib是一个单一的惰性列表，所有对fib的引用都指向同一个列表实例：

• 当程序需要某个位置的元素时，才会逐步求值前面的元素；
• 每个元素被计算一次后，就会被永久缓存（因为纯函数保证值不会被修改）；
• zipWith计算新元素时，直接复用fib和tail fib中已经求值过的结果——tail fib本质是fib去掉第一个元素的共享结构，不需要重新生成整个序列。
  整个过程等价于从0、1开始，每一步只做一次加法推导下一个元素，总时间复杂度为O(n)。

你的Ruby/Python实现的问题 #

你写的版本里，每次在生成器内部调用fib()都会创建全新的独立生成器实例，这些实例之间没有共享任何计算状态：

• 计算第3个元素时，lhs = fib()和rhs = fib()都会从头生成0、1；
• 计算后续元素时，每个新值的生成都会触发多个生成器从头遍历、重复计算前面的所有元素，最终导致时间复杂度变成指数级O(2ⁿ)。

修正后的线性时间版本 #

Ruby版本 #

核心是共享同一个生成器的状态，避免重复创建实例：

def fib
  Enumerator.new do |yielder|
    a, b = 0, 1
    loop do
      yielder.yield a
      a, b = b, a + b
    end
  end
end

gen = fib
20.times { puts gen.next }

Python版本 #

同样通过复用状态实现线性计算：

def fib():
    a, b = 0, 1
    while True:
        yield a
        a, b = b, a + b

gen = fib()
for _ in range(20):
    print(next(gen))

关键概念梳理 #

• 惰性求值≠自动优化：Ruby/Python的生成器是惰性的，但没有纯函数语言的不可变性保障，无法自动缓存结果；
• 共享不可变结构：Haskell的列表是不可变的，fib和tail fib共享大部分序列结构，避免了重复生成；
• 记忆化：纯函数特性让Haskell可以安全地缓存所有求值后的结果，所有引用同一表达式的地方都会复用缓存值。

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