Haskell do语句中let与<-实现斐波那契记忆化性能差异原因求解

核心问题和你的猜测不符 #

性能差异和let本身是否触发完全求值无关，是你在慢版本中错误使用了evalState，直接破坏了State单子的状态共享机制，导致记忆化完全失效。

慢版本的问题拆解 #

你编写的慢版本递归子调用逻辑如下：

let s1 = evalState (fibLet (n - 1)) mp                        
let s2 = evalState (fibLet (n - 2)) mp

evalState :: State s a -> s -> a的作用是传入初始状态，运行一个独立的State计算，只返回最终结果、丢弃运行过程中对状态的所有修改，这就导致：

• 每一次递归调用都新开了一个完全独立的State线程，用的都是当前层级拿到的、没有更新过的旧Mapmp
• 子递归中所有modify插入的缓存结果，都会随着子线程结束直接丢弃，父线程完全拿不到这些缓存
• 最终整个实现退化成了没有任何记忆化的朴素递归斐波那契，时间复杂度为O(2^n)，n稍微大一点运行速度就会指数级变慢。

快版本的优势 #

快版本中用<-绑定子调用的逻辑如下：

s1 <- fibArrow (n - 1)
s2 <- fibArrow (n - 2)

<-是Monad的绑定操作，所有子调用都运行在同一个State状态线程中：

• 子递归中modify对Map的修改会直接保留在当前线程的状态里，后续所有计算都能读取到之前插入的缓存
• 每个数值只会被计算一次，时间复杂度为O(n)，所以运行速度非常快。

补充说明 #

let本身没有问题，如果你用let绑定的是State动作本身，再用<-执行，和快版本的效果完全一致：

else do
  let act1 = fibLet (n - 1)
      act2 = fibLet (n - 2)
  s1 <- act1
  s2 <- act2
  let s3 = s1 + s2
  modify $ M.insert n s3
  return s3

这样修改后的fibLet也能达到和fibArrow一样的性能。

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