An example of using laziness

Introduction

I discovered a very elegant solution to a dynamic programming problem on hackerrank, if I say so myself. Please try it for yourself before reading the rest of this post.

The problem

The problem is about finding out in how many ways you can make change for a certain amount of money using an infinite supply of coins of different values.

An example is making change for 4 units using only coins with values 1, 2 and 3. You can do that in 4 ways: 1 + 1 + 1 + 1, 1 + 1 + 2, 1 + 3 and 2 + 2.

My solution

solve :: [Int] -> Int -> Integer
solve coins target = foldr cons nil coins !! target
  where
    cons :: Int -> [Integer] -> [Integer]
    cons x xs = let res = zipWith (+) xs (replicate x 0 ++ res) in res
    
    nil :: [Integer]
    nil = 1 : repeat 0

The solve function takes a list which contains the values of the coins and an integer denoting the target amount. It constructs a list where the i-th element contains the amount of ways we can make change for i units. This list is constructed by starting with a list with the same properties, but using no coins, and then one by one each coin is consed to that list.

The starting list is called nil. It is only possible to make 0 units if no coins are used, so it starts with a one and the rest of the list is filled with zeros.

The cons function takes a new coin value and a previous list of “ways”. The new list of ways can be constructed by adding the a list of ways where the new coin is used zero times, the list of ways where the new coin is used one time, the list of ways where the new coin is used two times, and so on. The list of ways where the new coin is used zero times is just the previous list of ways. The list of ways where the new coin is used n times is the previous list of ways preceded by n zeros (so shifted to the right n places).

The cons function can also be written as follows:

cons x xs = let res = take x xs ++ zipWith (+) (drop x xs) res in res

An exercise

I made this post to share (and show off) my understanding of this problem with fellow haskellers who want to become better programmers. I believe that understanding is not something you can get just by reading a blog post, so if you want more understanding I have the following exercise for you:

Rewrite the solve function to return a list of ways and not just the amount of ways.

So for example:

sort (map sort (solve' [1,2,3] 4)) == [[1,1,1,1],[1,1,2],[1,3],[2,2]]

where solve' is the rewritten solve function.