Explanation for this simple looking haskell program (dynamic programming)

Question

This is the program which counts number of ways to partition one dollar. I don't understand the line c = a ++ zipWith (+) b c as before this line c is not declared before this then how can we zip b and c? (I'm new to haskell, a good explanation is appreciated)

import Data.List
change [] = 1 : repeat 0
change (d : ds) = c where
  (a, b) = splitAt d (change ds)
  c = a ++ zipWith (+) b c
result = change [1, 5, 10, 15, 20, 25, 50] !! 100

Answer 1

change [] = 1 : repeat 0
change (d : ds) = c where
  (a, b) = splitAt d (change ds)
  c = a ++ zipWith (+) b c

Then,

result = (!! 100) $ xs 
  where 
    xs = change [1, 5, 10, 15, 20, 25, 50] 
       = let -- g = (\(a,b)-> fix ((a++) . zipWith (+) b)) 
             g (a,b) = let c = a ++ zipWith (+) b c in c
         in 
           g . splitAt 1 . change $ [5, 10, 15, 20, 25, 50]
         = g . splitAt 1 .
           g . splitAt 5 . change $ [10, 15, 20, 25, 50]
         = ....
         = let h n = g . splitAt n 
           in
             h 1 . h 5 . h 10 . h 15 . h 20 . h 25 . h 50 . (1:) . repeat $ 0

or, simpler,

Prelude> (!! 100) $ foldr h (1:cycle [0]) [1, 5, 10, 15, 20, 25, 50]
1239

(which is a correct answer, BTW). This is arguably easier to comprehend. Your question is thus localized to the g definition,

    g (a,b) = let c = a ++ zipWith (+) b c in c

The thing about Haskell's definitions is that they are recursive (they are equivalent to Scheme's letrec, not let).

Here it works, because when c is lazily consumed, it's definition says it's built from two parts, a ++ ... and so first a is consumed. And this works because a does not depend on c. Calculating a does not demand any knowledge of c.

In zipWith (+) b c, c is essentially a pointer into the sequence being defined, length a notches back from the production point, rest, in this re-write:

    g (a,b) = 
      let c = a ++ rest
          rest = zipWith (+) b c
      in c

We have h n xs = g (splitAt n xs) and this is describing then the sum of the input list with the result, moved n notches forward:

    x1 x2 x3 x4 x5 x6 x7 x8 ................ xs     A
                   y1 y2 y3 y4 y5 .......... ys     B
    --------
    y1 y2 y3 y4 y5 y6 y7.................... ys == A + B

This suggests h can be re-written with improved locality of access,

change ds n = foldr h (1:cycle [0]) ds !! n  -- [1, 5, 10, 15, 20, 25, 50] 100
  where
    h n xs = ys where ys = zipWith (+) xs (replicate n 0 ++ ys)
        -- = fix (zipWith (+) xs . (replicate n 0 ++))