Haskell中函数递归与数据递归的性能差异探究

一、函数绑定与模式绑定并非性能差异的直接核心，本质是值共享的区别 #

你观察到的smoothSeq/smoothSeq'、arithSeq/arithSeq'这类递归实现的性能差距，核心不在于绑定语法本身，而在于是否能利用Haskell的惰性求值实现自动值共享：

• 模式绑定（如递归列表定义）创建的是一个单一的递归值。比如：

  smoothSeq :: [Integer]
  smoothSeq = 0 : 1 : zipWith (+) smoothSeq (tail smoothSeq)
  

  这里的smoothSeq是一个惰性列表，每个元素被计算一次后就会被缓存。后续访问列表的任意位置时，直接复用已计算的结果，因此时间和内存消耗都是线性的。
• 函数式递归（如带参数的递归函数）默认不会共享计算结果。比如：

  smoothSeq' :: Int -> Integer
  smoothSeq' 0 = 0
  smoothSeq' 1 = 1
  smoothSeq' n = smoothSeq' (n-1) + smoothSeq' (n-2)
  

  每次调用smoothSeq' n都会重新展开递归，重复计算smoothSeq' (n-1)、smoothSeq' (n-2)等子项，导致时间复杂度呈指数级增长——这不是函数绑定语法的问题，而是这类实现没有将计算结果存储到可共享的结构中。

二、决定Memoization的底层原理：惰性求值与Thunk缓存 #

Haskell中自动Memoization的核心是惰性求值（非严格求值）和Thunk的缓存机制：

1. Thunk的本质：Haskell中未求值的表达式会被包装成“Thunk”（一种延迟计算的结构）。当Thunk第一次被需要（比如要获取它的弱头范式WHNF）时，才会被计算，计算后的结果会替换原来的Thunk。
2. 值共享的实现：如果多个地方引用同一个Thunk，计算一次后所有引用都会复用这个结果。比如递归列表smoothSeq中，smoothSeq和tail smoothSeq共享同一个列表结构的后续部分，因此每个元素的Thunk只会被计算一次。
3. 手动Memoization的逻辑：对于递归函数，要实现Memoization需要手动将计算结果缓存到一个可共享的数据结构中（比如数组、哈希表），本质是把函数调用的参数映射到已经计算好的结果，让后续相同参数的调用直接复用缓存值。

编译器优化（如GHC的-O2）可能会对部分递归函数做公共子表达式消除，但这种优化的范围有限——只有当编译器能明确识别出重复的表达式时才会生效，对于带任意数值参数的递归函数，编译器无法自动生成全局缓存，因此无法实现自动Memoization。

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