Note to self: solving a dynamic programming problem using löb. Literate Haskell source for this post is here: DPloeb.lhs.

The first solution is taken from http://blog.mno2.org/blog/2011/11/28/writing-dynamic-programming-in-haskell.

There are 73682 ways to select coins of the denominations specified in coins that sum to 200:

*DPloeb> main1
73682


First step: roll out the parameter to way:

Next, change the parameter from [Int] to Int by indexing on integers instead of various lists:

Substitute the value of cs in the body of the where clauses:

Substitute the value of c in the body of the where clauses:

Now tweak the type and collect each of the clauses into a list:

Instead of referring to whys4, index into the list with why !! 4:

Now we can define ways directly as a list:

Factor out whys by writing each list element as a function.

Now use loeb:

Finally, we can generalise this solution by writing a function to produce the elements of fs10:

These all say 73682: