如何在此函数中使用Y组合子进行缓存

Question

我有一个 coins = [200; 100; 50; 20; 10; 5; 2; 1] 列表和这个递归函数，用于计算给定金额的找零方式有多少种（对于欧拉计划问题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

除了对于大数值的StackOverflowException，该函数执行需要很长时间。因此我想起了Y组合子，并且想知道如何将其应用于这个问题。在得到一些帮助以及对函数签名进行两个小改动后，我获得了以下内容：

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

这很有效，现在我希望使用字典进行缓存。但是对于这个问题，我不知道该如何处理f函数的acc和coins参数。

在下面的代码中，字典已经具有了一个疯狂的类型。在对函数进行柯里化之后，它变成了一个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和列表作为两个初始化参数，但是我不能让其他变体正常工作。

如何使此示例中的缓存功能正常工作？也就是说，我需要如何修复参数，以便我的缓存类型为Dictionary<int, int64>？

---

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

- primfaktor

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

- kaefer

---

很难理解...那么你的解决方案就是为这个特定的例子而制作的，也就是说memoize不再是通用的了，对吧？例如，我的带有额外参数的f就无法工作。 - primfaktor

此外，将您的 d 更正为 Dictionary<int, int64> 会破坏您的代码。直觉上，这是我期望缓存具有的映射。 - primfaktor

这里的memoize是通用的（确切地说是泛型）。它所记忆的内容可以有任何结构，只要比较语义是按值（F#元组）比较即可。不同于添加参数的方法，这种方法是向元组中添加项。 - Alex Netkachov

直觉上，我期望缓存具有这种映射关系。但很遗憾，你的直觉是错误的，因为在这种方法中，函数 f 取决于金额和硬币集合。因此，仅通过 <int，int64> 进行记忆化只缓存了一小部分调用（可能是完整的硬币集合），在这种情况下，必须计算减少硬币集合的 f... - Alex Netkachov