我有一个 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
不是尾递归的,因此我可以省去acc
umulator参数的麻烦(还需要学习continuations)。
memoize
不再是通用的了,对吧?例如,我的带有额外参数的f
就无法工作。 - primfaktord
更正为Dictionary<int, int64>
会破坏您的代码。直觉上,这是我期望缓存具有的映射。 - primfaktormemoize
是通用的(确切地说是泛型)。它所记忆的内容可以有任何结构,只要比较语义是按值(F#元组)比较即可。不同于添加参数的方法,这种方法是向元组中添加项。 - Alex Netkachovf
取决于金额和硬币集合。因此,仅通过 <int,int64> 进行记忆化只缓存了一小部分调用(可能是完整的硬币集合),在这种情况下,必须计算减少硬币集合的f
... - Alex Netkachov