我正在尝试在 Haskell 中编写“如何使用最少的硬币amount来访问各种面额的硬币”功能。coins我用 DFS 实现了这个，它可以工作，但速度太慢了。在Python（我的主要语言）中，我可以记住结果并让相同的算法运行得非常快。我尝试在 Haskell 中做同样的事情，但收效甚微。
我将给出一个问题的玩具版本，我试图理解记忆化，然后向 DFS 展示我实际上试图记忆化的情况。
玩具问题
从Haskell Wiki 的 memoization 页面来看，实现此目的的一种方法是索引到无限列表中。类似的要点。
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) -- now no longer lazily evaled!
where fib 0 = 0 …