zmiana Liczenie w Haskell

Question

natknąłem się na następujące rozwiązanie problemu 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) 

on prowadził wiele szybciej niż mój naiwny odgórne rozwiązania rekurencyjnego, a ja wciąż staram się go zrozumieć.

Otrzymuję, że biorąc pod uwagę listę monet, aux oblicza każde rozwiązanie dla dodatnich liczb całkowitych. Dlatego rozwiązaniem dla kwoty jest indeksowanie listy na tej pozycji.

Jestem jednak mniej czytelny na temat addCoin. W jakiś sposób wykorzystuje wartość każdej monety do narysowania elementów z listy monet? Staram się znaleźć dla niego intuicyjne znaczenie.

Fałda aux wiąże również mój mózg w węzłach. Dlaczego 1:repeat 0 jest wartością początkową? Co to reprezentuje?

Answer 1

Jest to bezpośredni przekład bezwzględnej algorytmu DP dla problemu, który wygląda następująco (w Pythonie):

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] 

W szczególności addCoin coin solutions odpowiada

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

tą różnicą, że addCoin zwrotów zmodyfikowana lista zamiast mutowania starej. Jeśli chodzi o wersję Haskell, wynik powinien mieć niezmienioną sekcję na początku do coin -tego elementu, a następnie musimy wdrożyć solutions[i] += solutions[i - coin].

Realizujemy niezmienioną część przez take c oldlist i zmodyfikowaną część przez zipWith (+) newlist (drop c oldlist). W zmodyfikowanej części dodajemy razem i -ty element starej listy i i - coin -ty element wynikowej listy. Przesunięcie indeksów jest ukryte w operacjach drop i .

prostszy, klasycznym przykładem tego rodzaju przesunięcie i rekurencyjnej definicji jest liczb Fibonacciego:

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

Chcielibyśmy napisać to bezwzględnie jak

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 

Wracając do zmian monety, foldr addCoin (1:repeat 0) odpowiada do inicjalizacji solutions i pętli for na monetach, ze zmianą, że początkowa lista jest nieskończona zamiast skończonej (ponieważ lenistwo pozwala nam to zrobić).