# An example of using laziness

Posted on August 30, 2017

## 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 `cons`ed 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.