Counting change in Haskell

I came across the following solution to the DP problem of counting change:

count' :: Int -> [Int] -> Int
count' cents coins = aux coins !! cents
  where aux = foldr addCoin (1:repeat 0)
          where addCoin c oldlist = newlist
                  where newlist = (take c oldlist) ++ zipWith (+) newlist (drop c oldlist)

It ran much faster than my naive top-down recursive solution, and I'm still trying to understand it.

I get that given a list of coins, aux computes every solution for the positive integers. Thus the solution for an amount is to index the list at that position.

I'm less clear on addCoin , though. It somehow uses the value of each coin to draw elements from the list of coins? I'm struggling to find an intuitive meaning for it.

The fold in aux also ties my brain up in knots. Why is 1:repeat 0 the initial value? What does it represent?

---

It's a direct translation of the imperative DP algorithm for the problem, which looks like this (in Python):

def count(cents, coins):
    solutions = [1] + [0]*cents # [1, 0, 0, 0, ... 0]
    for coin in coins:
        for i in range(coin, cents + 1):
            solutions[i] += solutions[i - coin]
    return solutions[cents]

In particular, addCoin coin solutions corresponds to

for i in range(coin, cents + 1):
    solutions[i] += solutions[i - coin]

except that addCoin returns a modified list instead of mutating the old one. As to the Haskell version, the result should have an unchanged section at the beginning until the coin -th element, and after that we must implement solutions[i] += solutions[i - coin] .

We realize the unchanged part by take c oldlist and the modified part by zipWith (+) newlist (drop c oldlist) . In the modified part we add together the i -th elements of the old list and i - coin -th elements of the resulting list. The shifting of indices is implicit in the drop and take operations.

A simpler, classic example for this kind of shifting and recursive definition is the Fibonacci numbers:

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

We would write this imperatively as

def fibs(limit):
    res = [0, 1] + [0]*(limit - 2)
    for i in range(2, limit):
        res[i] = res[i - 2] + res[i - 1]
    return res

Turning back to coin change, foldr addCoin (1:repeat 0) corresponds to the initialization of solutions and the for loop on the coins, with the change that the initial list is infinite instead of finite (because laziness lets us do that).

链接地址: http://www.djcxy.com/p/27604.html

上一篇: 使用Xcode 7（Beta 3）构建Swift框架以用作嵌入式二进制文件

下一篇: 计算Haskell中的变化