如何使用 Y 组合器为此函数获取缓存

Question

我有一个 coins = [200; 100; 50; 20; 10; 5; 2; 1] 列表和这个递归函数来计算有多少种方法可以提供一定数量的零钱（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

除了 WhosebugException 大值之外，该函数需要很长时间。所以我记得 Y combinator and was curious how to in apply it to this problem. With a little help 和我到达这里的函数签名的两个小改动：

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

这行得通，现在我想使用字典进行缓存。但是为此我不知道如何处理 acc 和 coins 参数 f.

在下面的代码中，字典已经有一个疯狂的类型。柯里化函数后它变成了 int -> int64，所以我希望我的字典有这两个类型参数，但它没有。它可以编译并给出正确的答案，但对于大输入来说仍然很慢——对于那种类型来说不足为奇。

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

我尝试在所有地方粘贴两个初始化参数 0L 和列表，但我无法让任何其他变体工作。

我怎样才能使这个例子中的缓存工作，我。 e.我该如何修复参数，使我的缓存类型为 Dictionary<int, int64>?

PS：我知道我的 f 不是尾递归的，所以我可以用 accumulator 参数省去麻烦（还需要学习延续）。

Answer 1

你就快完成了，你只需要将 Y 组合器的功能集成到递归记忆功能中。

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

调整算法。

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

如何使用 Y 组合器为此函数获取缓存

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

recursion

f#

caching

memoization

y-combinator