Haskell递归函数的惰性求值与记忆化实现问题咨询

我想用Haskell写一个「用最少硬币凑出指定金额amount」的函数，一开始用DFS实现但速度太慢。在Python里，相同算法加记忆化就能跑很快，但在Haskell里试了记忆化却没什么效果。

我先拿斐波那契的记忆化示例来理解问题：
从Haskell Wiki的记忆化页面看到，可以用索引无限列表实现记忆化：

memoized_fib :: Int -> Integer
memoized_fib = (map fib [0 ..] !!)
   where fib 0 = 0
         fib 1 = 1
         fib n = memoized_fib (n-2) + memoized_fib (n-1)

这个实现符合预期，但改成带命名变量的形式后就不再是惰性求值了：

memoized_fib :: Int -> Integer
memoized_fib n = (map fib [0 ..] !! n)  -- 现在不再是惰性求值了！
   where fib 0 = 0
         fib 1 = 1
         fib n = memoized_fib (n-2) + memoized_fib (n-1)

我想搞懂这个现象，因为我的找零函数是对单个参数递归，要写成无点式的!!操作有点难。

以下是我的非记忆化找零函数：

import Data.List

smallestMaybeList :: Maybe [Integer] -> Maybe[Integer] -> Maybe[Integer]
smallestMaybeList (Just a) Nothing = (Just a)
smallestMaybeList Nothing (Just b) = (Just b)
smallestMaybeList Nothing Nothing = Nothing
smallestMaybeList (Just a) (Just b) = if (length a) < (length b) then (Just a) else (Just b)


makeChange :: Integer -> [Integer] -> Maybe [Integer]
makeChange 0 _ = Just []
makeChange _ [] = Nothing
makeChange amount coins
  | amount < 0 = Nothing
  | amount `elem` coins = Just [amount]
  | otherwise = foldl' smallestMaybeList Nothing [(++) [c] <$> makeChange (amount-c) remCoin | c <- remCoin]
      where remCoin = [c | c <- coins, c < amount]

我尝试的记忆化版本还是严格求值：

import Data.List

--smallestMaybeList :: Maybe [Integer] -> Maybe[Integer] -> Maybe[Integer]
smallestMaybeList (Just a) Nothing = (Just a)
smallestMaybeList Nothing (Just b) = (Just b)
smallestMaybeList Nothing Nothing = Nothing
smallestMaybeList (Just a) (Just b) = if (length a) < (length b) then (Just a) else (Just b)

makeChange :: Integer -> [Integer] -> Maybe [Integer]
makeChange 0 coins = Just []
makeChange amount coins
  | amount < 0 = Nothing
  | otherwise = [mch a coins | a <- [0..]] !! (fromInteger amount)

-- 这是「找零辅助函数」
mch :: Integer -> [Integer] -> Maybe [Integer]
mch 0 _ = Just []
mch _ [] = Nothing
mch amount coins
  | amount < 0 = Nothing
  | amount `elem` coins = Just [amount]
  | otherwise = foldl' smallestMaybeList Nothing [(++) [c] <$> makeChange (amount-c) coins | c <- coins]

我试过把辅助函数内联等变体，但效果都不好。

我的问题：

1. 为什么把无点式写法改成带命名变量的形式后，就从惰性求值变成严格求值了？
2. 怎么给当前的找零算法实现有效的记忆化？

解答 #

问题1：无点式与命名变量的求值差异

在无点式的memoized_fib = (map fib [0..] !!)中，map fib [0..]是一次创建并共享的无限列表。当第一次调用memoized_fib n时，列表会被惰性计算到第n项，后续调用其他索引时，已经计算过的项会直接从共享列表中读取，这就是记忆化的核心。

而改成memoized_fib n = (map fib [0..] !! n)后，每次调用函数都会重新创建整个map fib [0..]列表。也就是说，每次调用memoized_fib都会从头开始生成列表并查找第n项，之前计算的结果完全没有被复用，自然就失去了记忆化的效果，看起来像是严格求值（实际上是每次都重新计算，效率极低）。

本质是：无点式写法中，无限列表是函数的一个“共享常量”；而命名变量写法中，无限列表是每次调用函数时才生成的局部值，无法共享之前的计算结果。

问题2：找零函数的记忆化实现

你的找零函数有两个参数：amount和coins，所以需要针对这两个参数的组合进行记忆化。我们可以用“柯里化+无限列表”的思路，先固定coins参数，生成一个针对amount的记忆化函数，再处理不同的coins情况。

这里提供两种可行的实现方式：

方式1：基于共享列表的记忆化

我们可以把makeChange设计成：先接收coins，返回一个针对amount的记忆化函数。这样每个coins对应的无限列表会被共享复用：

import Data.List
import Data.Maybe

smallestMaybeList :: Maybe [Integer] -> Maybe [Integer] -> Maybe [Integer]
smallestMaybeList a b = case (a, b) of
  (Just xs, Nothing) -> Just xs
  (Nothing, Just ys) -> Just ys
  (Just xs, Just ys) -> Just $ if length xs < length ys then xs else ys
  _ -> Nothing

makeChange :: [Integer] -> Integer -> Maybe [Integer]
makeChange coins = memoized
  where
    -- 生成从0开始的所有金额的找零结果列表
    memoizedList = map mch [0..]
    -- 记忆化函数：直接索引预先生成的列表
    memoized amount = memoizedList !! fromInteger amount
    
    mch :: Integer -> Maybe [Integer]
    mch 0 = Just []
    mch amount
      | amount < 0 = Nothing
      | amount `elem` coins = Just [amount]
      | otherwise = foldl' smallestMaybeList Nothing candidates
      where
        -- 只保留小于当前金额的硬币，避免无效递归
        validCoins = filter (<= amount) coins
        candidates = map (\c -> (c :) <$> memoized (amount - c)) validCoins

使用方式：makeChange [1,5,10,25] 100，这样每个coins集合对应的memoizedList只会生成一次，后续调用同一coins的不同amount时，会直接复用已计算的结果。

方式2：使用Data.Map显式缓存

如果需要更灵活的记忆化（比如不需要预先生成所有金额的列表），可以用Data.Map来存储已计算的(amount, coins)组合结果：

import Data.List
import Data.Maybe
import qualified Data.Map as Map

type Cache = Map.Map (Integer, [Integer]) (Maybe [Integer])

smallestMaybeList :: Maybe [Integer] -> Maybe [Integer] -> Maybe [Integer]
smallestMaybeList a b = case (a, b) of
  (Just xs, Nothing) -> Just xs
  (Nothing, Just ys) -> Just ys
  (Just xs, Just ys) -> Just $ if length xs < length ys then xs else ys
  _ -> Nothing

makeChange :: Integer -> [Integer] -> Maybe [Integer]
makeChange amount coins = fst $ go amount coins Map.empty
  where
    go :: Integer -> [Integer] -> Cache -> (Maybe [Integer], Cache)
    go 0 _ cache = (Just [], cache)
    go _ [] cache = (Nothing, cache)
    go amount coins cache
      | amount < 0 = (Nothing, cache)
      | amount `elem` coins = (Just [amount], cache)
      | otherwise = case Map.lookup (amount, coins) cache of
          -- 命中缓存，直接返回结果和原缓存
          Just res -> (res, cache)
          -- 未命中，计算所有候选结果，然后更新缓存
          Nothing ->
            let validCoins = filter (<= amount) coins
                -- 递归计算每个硬币对应的找零结果，同时更新缓存
                (candidates, newCache) = foldl' processCandidate (Nothing, cache) validCoins
                res = candidates
                -- 将当前结果存入缓存
                finalCache = Map.insert (amount, coins) res newCache
            in (res, finalCache)
          where
            processCandidate :: (Maybe [Integer], Cache) -> Integer -> (Maybe [Integer], Cache)
            processCandidate (currentBest, cache) c =
              let (subRes, newCache) = go (amount - c) coins cache
                  candidate = (c :) <$> subRes
                  newBest = smallestMaybeList currentBest candidate
              in (newBest, newCache)

这个版本显式管理缓存，适合不需要预先生成所有金额的场景，同样能有效复用已计算的结果。

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