为Haskell函数签名添加单个变量致代码性能骤降的原因咨询

原Haskell代码计算Collatz序列时运行高效：

import qualified Data.Map as M
import Data.Ord (comparing)
import Data.List (maximumBy)

ansMap :: M.Map Integer Int
ansMap = M.fromAscList [(i, collatz i) | i <- [1..1000000]]
  where collatz 1 = 0
        collatz x = if x' <= 1000000 then 1 + ansMap M.! x'
                                     else 1 + collatz x'
          where x' = if even x then x `div` 2 else x*3 + 1

-- 这段代码运行速度很快
fst $ maximumBy (comparing snd) $ M.toList ansMap 

为支持计算更多数字的Collatz序列，将固定值1000000改为变量n传入函数后，代码运行突然变慢：

import qualified Data.Map as M
import Data.Ord (comparing)
import Data.List (maximumBy)

ansMap :: Integer -> M.Map Integer Int
ansMap n = M.fromAscList [(i, collatz i) | i <- [1..n]]
  where collatz 1 = 0
        collatz x = if x' <= n then 1 + ansMap n M.! x'
                                     else 1 + collatz x'
          where x' = if even x then x `div` 2 else x*3 + 1

-- 这段代码运行速度骤降
fst $ maximumBy (comparing snd) $ M.toList $ ansMap 1000000

仅将固定值改为传入变量就导致性能大幅下降，原因如下：

• 顶层常量与函数的本质差异：原代码中ansMap是顶层常量，Haskell会在程序启动阶段一次性计算完整的Map并缓存，collatz查询时直接复用这个已构建好的Map，完全没有重复计算。
• 重复构建Map的致命开销：修改后的ansMap n是一个函数，每次collatz x查询x' <= n对应的Map元素时，都会调用ansMap n重新构建整个Map。这会触发指数级的重复计算——比如计算collatz 1000000依赖collatz 500000，而每次调用collatz 500000又会重新构建一次1到1000000的Map，性能自然暴跌。

修复方案 #

让collatz函数共享同一个正在构建的Map，避免重复构建。可以通过递归let绑定实现：

import qualified Data.Map as M
import Data.Ord (comparing)
import Data.List (maximumBy)

ansMap :: Integer -> M.Map Integer Int
ansMap n = let mapCache = M.fromAscList [(i, collatz mapCache i) | i <- [1..n]]
               collatz _ 1 = 0
               collatz cache x = let x' = if even x then x `div` 2 else x*3 + 1
                                 in if x' <= n 
                                    then 1 + cache M.! x'
                                    else 1 + collatz cache x'
           in mapCache

-- 恢复高效运行
fst $ maximumBy (comparing snd) $ M.toList $ ansMap 1000000

这里mapCache是递归绑定的Map，构建时collatz直接使用当前正在构建的mapCache，不会重新调用ansMap n，彻底消除了重复构建的开销。

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