Dynamic programming in the functional paradigm

Question

I'm looking at Problem thirty one on Project Euler, which asks, how many different ways are there of making £2 using any number of coins of 1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).

There are recursive solutions, such as this one in Scala (credit to Pavel Fatin)

def f(ms: List[Int], n: Int): Int = ms match {   case h :: t =>     if (h > n) 0 else if (n == h) 1 else f(ms, n - h) + f(t, n)   case _ => 0 }  val r = f(List(1, 2, 5, 10, 20, 50, 100, 200), 200) 

and although it runs fast enough, it's relatively inefficient, calling the f function around 5.6 million times.

I saw someone else's solution in Java which was programmed dynamically (credit to wizeman from Portugal)

final static int TOTAL = 200;  public static void main(String[] args) {     int[] coins = {1, 2, 5, 10, 20, 50, 100, 200};     int[] ways = new int[TOTAL + 1];     ways[0] = 1;      for (int coin : coins) {         for (int j = coin; j <= TOTAL; j++) {             ways[j] += ways[j - coin];         }     }      System.out.println("Result: " + ways[TOTAL]); } 

This is much more efficient and passes the inner loop only 1220 times.

While I could obviously translate this more or less verbatim into Scala using Array objects, is there an idiomatic functional way to do this using immutable data structures, preferably with similar conciseness and performance?

I have tried and become stuck trying to recursively update a List before deciding I'm probably just approaching it the wrong way.

Answer 1

Whenever some part of a list of data is computed based on a previous element, I think of Stream recursion. Unfortunately, such recursion cannot happen inside method definitions or functions, so I had to turn a function into a class to make it work.

class IterationForCoin(stream: Stream[Int], coin: Int) {   val (lower, higher) = stream splitAt coin   val next: Stream[Int] = lower #::: (higher zip next map { case (a, b) => a + b }) } val coins = List(1, 2, 5, 10, 20, 50, 100, 200) val result = coins.foldLeft(1 #:: Stream.fill(200)(0)) { (stream, coin) =>   new IterationForCoin(stream, coin).next } last 

The definitions of lower and higher are not necessary -- I could easily replace them with stream take coin and stream drop coin, but I think it's a little clearer (and more efficient) this way.

Answer 2

I don't know enough about Scala to comment specifically on that, but the typical way to translation a DP solution in to a recursive one is to memoization (use http://en.wikipedia.org/wiki/Memoization). This is basically caching the result of your function for all values of the domain

I found this as well http://michid.wordpress.com/2009/02/23/function_mem/. HTH