How to get caching with the Y-combinator for this function

Question

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).

Answer 1

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])