当函数需要中间结果时使用 Haskell 映射

Question

我正在研究Haskell的文本，并遇到了一个关于进行更改的问题。我得到了一个有序的（分母，数字币）元组列表以及一个数量，需要返回每个硬币用于进行更改的列表。我有以下代码可以解决问题：

useCoins :: (Int,Int) -> Int -> Int
useCoins (denomination, numCoins) target = min numCoins (target `div` denomination)
makeChange :: [(Int, Int)] -> Int -> [Int]
makeChange [] target = []
makeChange ((denomination, numCoins):xs) target = 
  let
     coinsUsed = useCoins (denomination, numCoins) target
  in coinsUsed : makeChange xs (target - (coinsUsed * denomination))

问题是这是在关于高阶函数的一章中，我很难想出一种方法来使用 map，因为目标值在列表中下降时会发生变化。我希望得到任何帮助。

谢谢。

-兆赫

Answer 1

map是

错误的函数，因为正如您所注意到的，它仅适用于每个元素可以独立处理的情况，而不适用于元素相互依赖的情况。

但是，makeChange是一个可通过折叠实现的函数。具体来说，您的实现包含左折的所有功能，但手动完成;您可以改为根据foldl'来实现您的函数。