5

I have a coins = [200; 100; 50; 20; 10; 5; 2; 1] list and this recursive function to compute how many ways there are to give a certain amount of change (Spoiler alert for Project Euler problem 31):

let rec f acc coins amount = if amount < 0 then 0L elif amount = 0 then acc else match coins with | [] -> 0L | c::cs -> f (acc + 1L) coins (amount - c) + f acc cs amount

Apart from a StackOverflowException for large values the function takes very long. So I remembered the Y combinator and was curious how to in apply it to this problem. With a little help and two small changes to the signature of the function I arrived at this:

let f f acc coins amount = if amount < 0 then 0L elif amount = 0 then acc else match coins with | [] -> 0L | c::cs -> f (acc + 1L) coins (amount - c) + f acc cs amount let rec Y f x = f (Y f) x

This works and now I want to use a dictionary for caching. But for that I don't know what to do with the acc and coins arguments to f.

In the following code the dictionary already has a crazy type. After currying the function it becomes an int -> int64, so I would expect my dictionary to have these two type parameters, but it doesn't. It compiles and gives the right answer but it is still very slow for large inputs—unsurprisingly with that type.

open System.Collections.Generic let memoize (d:Dictionary<_, _>) f x = match d.TryGetValue(x) with | true, re -> re | _ -> let re = f x d.Add(x, re) re let numberOfWaysToChange = let d = Dictionary<_,_>() fun x -> Y (f >> fun f x -> memoize d f x) 0L coins x

I tried sticking the two initialization arguments 0L and the list in all places but I couldn't get any other variants working.

How can I make caching in this example work, i. e. how do I have to fix parameters so that my cache is of type Dictionary<int, int64>?

PS: I know that my f is not tail-recursive, so I could save the hassle with the accumulator argument (also need to learn continuations).

Improve this question

1 Answer 1

Reset to default
2

You were almost there, you just need to integrate the functionality of the Y combinator into the recursive memoization function.

let rec Y f x = f (Y f) x // val Y : f:(('a -> 'b) -> 'a -> 'b) -> x:'a -> 'b let memoize f = let d = new System.Collections.Generic.Dictionary<_,_>() let rec g x = match d.TryGetValue x with | true, res -> res | _ -> let res = f g x in d.Add(x, res); res g // val memoize : f:(('a -> 'b) -> 'a -> 'b) -> ('a -> 'b) when 'a : equality

Adjust the algorithm.

let cc f = function | amount, _ when amount = 0 -> 1 | amount, _ when amount < 0 -> 0 | _, [] -> 0 | amount, hd::tl -> f (amount, tl) + f (amount - hd, hd::tl) #time;; Y cc (200, [200; 100; 50; 20; 10; 5; 2; 1]) memoize cc (200, [200; 100; 50; 20; 10; 5; 2; 1])
Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

Difficult to wrap my head around… Your solution is then crafted for this specific example, i. e. the memoize is not general anymore, right? For instance my f with the additional argument doesn't work.
Also, fixing your d to Dictionary<int, int64> breaks your code. Intuitively that's the mapping I expect the cache to have.
memoize here is general enough (it is generic, to be precise :-) ). What it memorizes can have any structure as long as its comparison semantic is by value (F# tuples). Just instead of adding arguments the approach is to add items to the tuple.
"Intuitively that's the mapping I expect the cache to have." - your intuition is wrong here, I'm afraid, because in this approach the function f depends on both amount and coinset. So memoising only by <int, int64> only caches small part of invocations (with full coinset probably) - the fs with reduced coinset had to be calculated in this case...

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.