Counting changes in Haskell

Question

I came across the following solution to the DP change count problem:

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 worked much faster than my naive reverse solution from top to bottom, and I'm still trying to figure it out.

I get that, given the list of coins, aux calculates each solution for positive integers. Thus, the solution for the amount should index the list at this position.

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

The folds in aux also connect my brain to the nodes. Why is 1:repeat 0 initial value? What does he represent?

Answer 1

This is a direct translation of the imperative DP algorithm for a problem that 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 for the Haskell version, the result should have an unchanged section at the beginning before the coin -th element, and after that we must implement solutions[i] += solutions[i - coin] .

We implement the unchanged part on take c oldlist and the modified part on zipWith (+) newlist (drop c oldlist) . In the modified part, we combine i -th elements from the old list and i - coin -th elements of the resulting list. Index movement is implicit in drop and take operations.

The simplest classic example of this kind of shift and recursive definition are Fibonacci numbers:

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

We will write it 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 

Returning to changing the coin, 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, not finite (because laziness allows us to do this).