Haskell中howSum记忆化递归函数缓存失效如何解决

你手动传递Map作为缓存的写法无法生效，核心原因是把命令式语言中可变缓存的使用逻辑套用到了纯函数式场景：

• Haskell的不可变数据结构决定了，递归分支中对memo的插入操作只会生成新的Map副本，不会修改传入的原Map
• 不同递归分支拿到的都是当前路径上的旧版Map，无法跨分支共享其他路径计算出的缓存结果，相当于缓存完全没起到作用
• 你当前的实现里，计算val时传给子递归的memo还没插入当前target的计算结果，就算调整插入顺序，也解决不了副本不共享的问题

另外你的实现返回所有可能组合，和题目要求返回任意一个有效组合的需求不符，会产生大量无意义的计算。

Haskell中做这类动态规划的记忆化不需要手动传递缓存，利用惰性求值的特性递归绑定整张缓存表即可，所有递归调用共享同一张表，首次访问某个键时才计算对应值，计算完成后自动缓存供后续所有调用使用。

符合题目要求的版本（返回任意一个有效组合） #

用Maybe [Int]作为返回值，找到有效组合就提前返回，找不到返回Nothing，性能最优：

import Data.Map (Map, (!), fromList)
import Control.Monad (msum)

howSum :: Int -> [Int] -> Maybe [Int]
howSum target nums
    | target < 0 = Nothing
    | otherwise = memo ! target
  where
    -- 先过滤非正数避免无限递归
    validNums = filter (>0) nums
    -- 惰性缓存表，键为剩余目标和，值为对应求解结果
    memo = fromList [(t, compute t) | t <- [0..target]]
    compute 0 = Just [] -- 剩余和为0，找到有效组合
    compute t = msum $ map (\x -> (x:) <$> memo ! (t - x)) $ filter (<=t) validNums

需要返回所有组合的记忆化版本 #

如果确实需要获取所有有效组合，只需要把返回值换回列表即可，记忆化逻辑完全一致：

import Data.Map (Map, (!), fromList)

howSumAll :: Int -> [Int] -> [[Int]]
howSumAll target nums
    | target < 0 = []
    | otherwise = memo ! target
  where
    validNums = filter (>0) nums
    memo = fromList [(t, compute t) | t <- [0..target]]
    compute 0 = [[]]
    compute t = concatMap (\x -> map (x:) (memo ! (t - x))) $ filter (<=t) validNums

• 缓存表memo是当前howSum调用范围内共享的惰性结构，不存在多副本问题，所有递归分支访问的都是同一张表
• 表中的条目只会在第一次被索引时触发计算，计算完成后就会保留在Map中，后续访问直接读取缓存值
• 过滤掉非正数的逻辑可以避免nums中存在0或负数时出现无限递归
• 单解版本用msum会在找到第一个有效Just值时立刻终止后续计算，不会枚举所有可能组合，符合题目返回任意解的要求

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