The explanation for this simple haskell search program (dynamic programming)

Question

This is a program that counts the number of ways to break one dollar. I do not understand the line c = a ++ zipWith (+) bc , because before this line c is not declared before, then how can we zip b and c? (I'm new to haskell, a good explanation is welcome)

 import Data.List change [] = 1 : repeat 0 change (d : ds) = c where (a, b) = splitAt d (change ds) c = a ++ zipWith (+) bc 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 (+) bc 

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 (+) bc 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 hn = g . splitAt n in h 1 . h 5 . h 10 . h 15 . h 20 . h 25 . h 50 . (1:) . repeat $ 0 

or, more simply,

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

(This is the correct answer, BTW). This may be easier to understand. So your question is localized in the definition of g ,

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

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

Here it works, because when c lazily consumed, it says that it is built of two parts, a ++ ... and therefore a is consumed first. And this works because a is independent of c . Calculation of a does not require knowledge of c .

In zipWith (+) bc c is essentially a pointer in the defined sequence, length a cuts back from the production point rest , rewrite this:

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

We have hn xs = g (splitAt n xs) , and this then describes the sum of the input list with the result moved n cut 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 that h can be rewritten with improved locality of access,

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

Answer 2

y = fy equivalent to an infinite chain of applications: y = f (f (f (f (...

therefore c = a ++ (zipWith (+) bc) equivalent to c = a ++ (zipWith (+) b (a ++ (zipWith (+) b (...)))

Answer 3

This is a particularly complex use of recursive definitions. Both "changes" and "c" are defined on their own.

'change _' is an infinitely long, single-linked list of Integer.

This 'c' is also an infinitely long, simply connected Integer list.

What is the first element of "a ++ ..."? If "a" is not empty (and here it is not empty, since the list goes to change, all are positive), then this is the first element of "a".

In fact, “a” has a length of “1” in the first change, then “5”, and then “10”, until the last “a” has a length of “50”.

So, the first element from 'c' is taken from 'a'. Then, as soon as they end, the next c elements come from zipWith (+) bc.

Now 'b' and 'c' are infinitely long, single-linked Integer lists.

The first element "b" comes from the part of the recursive call "change_" after part "a". The first part of "c" is part of "a".

Let the length of part "a" be 5, and also call "a" by the name "p1".

 c = (5 elements of 'a', call this p1) ++ (5 elements of zipWith (+) p1 b, call this p2) ++ (5 elements of zipWith (+) p2 (drop 5 b), call this p3) ++ (5 elements of zipWith (+) p3 (drop 10 b) ++...