Perl 6柯里化函数挂起问题：零钱兑换组合数实现遇阻

我太懂这种踩坑的感觉了——用递归+柯里化实现硬币组合数的时候，一不小心就会碰到函数挂起的问题，大概率是递归终止条件没处理好，或者柯里化的参数绑定出了岔子。咱们先把你的思路拆解清楚，再一步步解决。

首先，先确认下你实现的coin函数逻辑应该是类似这样的（基于经典的硬币组合递归思路）：

coin :: Int -> [Int] -> Int
coin 0 _ = 1  -- 金额为0时，只有1种组合（不用任何硬币）
coin _ [] = 0  -- 没有硬币可选时，组合数为0
coin amount (c:cs)
  | amount >= c = coin amount cs + coin (amount - c) (c:cs)
  | otherwise = coin amount cs

这个函数的核心是分两种情况：要么不用当前面值的硬币，递归计算剩余面值的组合数；要么用至少一个当前面值的硬币，递归计算扣除该面值后的金额的组合数。

接下来你提到的ladder函数，应该是想做柯里化，把硬币面值列表固定下来，返回一个只接受金额的函数？或者是想构建一个“阶梯式”的函数链，逐步添加新面值来扩展组合计算能力？不管是哪种，挂起的问题基本都和递归终止条件缺失或者惰性求值导致的无限递归有关。

先给一个能正常工作的柯里化ladder实现 #

如果你的需求是固定硬币面值，返回一个计算任意金额组合数的函数，那可以直接基于coin函数做柯里化，而且不会挂起：

ladder :: [Int] -> (Int -> Int)
ladder coins = \amount -> coin amount coins

比如调用ladder [1,5,10] 20就会返回用1、5、10分硬币凑20分的组合数。

但如果你的ladder是想递归地构建面值阶梯（比如从单面值开始，逐步添加面值），那可能之前的写法没处理好终止条件，导致无限挂起。比如正确的递归版ladder应该这样写：

ladder :: [Int] -> (Int -> Int)
ladder [] = const 0  -- 空面值集合，直接返回0
ladder [singleCoin] = \amount -> if amount `mod` singleCoin == 0 then 1 else 0  -- 单面值的情况，只有金额能被整除时才有1种组合
ladder (currentCoin:remainingCoins) = \amount ->
  let -- 先获取更小面值集合的计算函数
      smallerCombination = ladder remainingCoins
  in -- 组合数 = 不用当前硬币的组合数 + 用至少一个当前硬币的组合数
     smallerCombination amount + if amount >= currentCoin then (ladder (currentCoin:remainingCoins)) (amount - currentCoin) else 0

这个版本明确处理了空列表和单元素列表的终止条件，递归调用时也会先求值更小面值的函数，避免了惰性求值导致的无限挂起。

进阶：用记忆化优化性能（同时避免潜在的求值问题） #

硬币组合数计算很容易重复计算相同的(金额, 面值列表)组合，不仅慢，还可能因为重复递归导致意外的挂起。可以给函数加上记忆化，用Map缓存已经计算过的结果：

import Data.Map (Map)
import qualified Data.Map as Map

-- 带记忆化的核心计算函数，返回结果和更新后的缓存
coinMemo :: Int -> [Int] -> Map (Int, [Int]) Int -> (Int, Map (Int, [Int]) Int)
coinMemo 0 _ memo = (1, memo)
coinMemo _ [] memo = (0, memo)
coinMemo amount coins memo
  | Map.member (amount, coins) memo = (memo Map.! (amount, coins), memo)  -- 命中缓存直接返回
  | amount >= head coins = 
      let (val1, memo1) = coinMemo amount (tail coins) memo
          (val2, memo2) = coinMemo (amount - head coins) coins memo1
          result = val1 + val2
      in (result, Map.insert (amount, coins) result memo2)
  | otherwise = 
      let (val, memo1) = coinMemo amount (tail coins) memo
      in (val, Map.insert (amount, coins) val memo1)

-- 包装成柯里化的ladder函数，对外提供简洁的接口
ladderMemo :: [Int] -> Int -> Int
ladderMemo coins amount = fst $ coinMemo amount coins Map.empty

这个版本不仅不会挂起，还能大幅提升大金额计算的性能。

总结下挂起的常见原因 #

1. 递归终止条件缺失：如果你的ladder函数没有处理空列表或者单面值的情况，递归会无限进行下去，导致函数挂起；
2. 惰性求值的坑：Haskell的惰性求值会推迟计算，如果递归调用时的参数没有被强制求值，可能会导致函数一直处于未求值的挂起状态；
3. 参数绑定错误：柯里化时如果没有正确绑定面值列表，可能会导致每次递归都生成新的未绑定函数，进而挂起。

只要把这些点处理好，就能顺利实现你想要的硬币组合数计算功能啦。

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