Haskell中如何预存固定深度的rollspace列表避免重复求值
快艇骰子掷骰空间的预存方案
编译器的自动优化边界
首先要明确:GHC不会自动为带参数的rollspace函数做全量结果缓存。
- Haskell的惰性求值仅会对同一个作用域内的表达式共享计算结果,跨函数调用、跨作用域的纯函数调用,默认是没有记忆化机制的——哪怕输入参数完全相同,每次调用都会重新走一遍生成逻辑。
- 如果你把
rollspace 3这类调用写在业务函数的局部let绑定里,每次调用这个业务函数时,都会重新生成一次对应列表;只有当表达式被提到模块顶级作用域时,GHC才会把计算结果长期驻留内存。 - 这种设计是刻意的:如果所有纯函数的所有调用结果都自动缓存,程序会无限制占用内存,完全不符合运行时效率的设计初衷。
适配你场景的零成本预存方案
因为你的实际使用范围被严格限制在depth = 1到depth =5,根本不需要引入复杂的通用记忆化机制,直接把每个深度的掷骰列表定义成模块级的顶级绑定即可,这是Haskell里性能最高、开销最小的预存方式:
- 顶级绑定的初始化是惰性的:你第一次引用某个深度的列表时,才会触发对应的生成逻辑,不会在程序启动时就把所有列表都算出来占内存。
- 每个顶级绑定被计算完成后,GHC会把对应的thunk替换成已经求值好的静态值,后续所有对这个绑定的引用都会直接复用同一份内存,永远不会重复计算。
- 内存开销极低:最大的
rollspace 5总共只有7776个长度为5的整数列表,折算下来总内存占用仅300KB左右,常驻内存没有任何压力。
可以直接按下面的方式改代码:
type Roll = [Int] rollspace :: Int -> [Roll] rollspace depth = worker [[]] 0 where m xs n = map (\e -> n:e) xs addRoll xs = m xs 1 ++ m xs 2 ++ m xs 3 ++ m xs 4 ++ m xs 5 ++ m xs 6 worker xs i = if i == depth then xs else worker (addRoll xs) (i+1) -- 预存各深度的掷骰空间,惰性初始化,首次访问后常驻内存 rollSpace1 = rollspace 1 rollSpace2 = rollspace 2 rollSpace3 = rollspace 3 rollSpace4 = rollspace 4 rollSpace5 = rollspace 5 -- 按深度直接取对应列表,无重复计算 getRollSpace :: Int -> [Roll] getRollSpace n = case n of 1 -> rollSpace1 2 -> rollSpace2 3 -> rollSpace3 4 -> rollSpace4 5 -> rollSpace5
额外的优化提示
你原来的rollspace生成逻辑在小深度下性能已经完全足够,但如果要进一步减少生成时的开销,可以把多段++的列表拼接换成concatMap实现,生成速度会稍快一点,不过因为只需要在第一次访问时生成一次,这个优化的实际收益非常小。
注意:不要为了这个场景引入第三方通用记忆化库,硬编码的顶级绑定是没有任何额外查表开销的,性能比任何通用memo表都高。
内容的提问来源于stack exchange,提问作者Phineas Greene
相关产品推荐
相关产品推荐

