Counting Änderung in Haskell

Question

stieß ich auf die folgende Lösung für das Problem der DP 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) 

Es lief viel schneller als meine naive Top-down-rekursive Lösung, und ich bin immer noch versuchen, es zu verstehen.

Ich bekomme, dass eine Liste von Münzen gegeben, aux berechnet jede Lösung für die positiven ganzen Zahlen. Daher besteht die Lösung für einen Betrag darin, die Liste an dieser Position zu indizieren.

Ich bin weniger klar auf addCoin, obwohl. Es benutzt irgendwie den Wert jeder Münze, um Elemente aus der Münzliste zu zeichnen? Ich kämpfe darum, eine intuitive Bedeutung dafür zu finden.

Die Falte in aux bindet auch mein Gehirn in Knoten. Warum ist 1:repeat 0 der Anfangswert? Was stellt es dar?

Answer 1

Es ist eine direkte Übersetzung des Imperativs DP-Algorithmus für das Problem, das wie folgt aus (in Python) aussieht:

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] 

Insbesondere addCoin coin solutions zu

entspricht

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

außer dass addCoin zurückkehrt eine modifizierte Liste, anstatt die alte zu mutieren. Was die Haskell-Version anbelangt, sollte das Ergebnis zu Beginn einen unveränderten Abschnitt bis zum Element coin haben, und danach müssen wir solutions[i] += solutions[i - coin] implementieren.

Wir realisieren den unveränderten Teil von take c oldlist und den modifizierten Teil von zipWith (+) newlist (drop c oldlist). Im modifizierten Teil fügen wir die i -ten Elemente der alten Liste und i - coin-te Elemente der resultierenden Liste hinzu. Die Verschiebung der Indizes ist implizit in den Operationen drop und take enthalten.

Ein einfacheres, klassisches Beispiel für diese Art von Verschiebung und rekursive Definition ist die Fibonacci-Zahlen:

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

Wir diese zwingend als

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 

Zurückkommend auf Münzwechsel, foldr addCoin (1:repeat 0) entspricht schreiben würde zur Initialisierung von solutions und der for-Schleife auf den Münzen, mit der Änderung, dass die anfängliche Liste unendlich statt endlich ist (weil Faulheit uns das tun lässt).