F# 中通用约束函数的记忆

Question

我正在尝试使用我认为是 F# 中的标准记忆模式来记忆受约束的泛型函数。这是一个简化的示例，总结了我失败的尝试：

module Sample

open System.Collections.Generic;

let memoize f =
    let cache = Dictionary<_, _>()
    fun x ->
        if cache.ContainsKey(x) then 
            cache.[x]
        else 
            let res = f x
            cache.[x] <- res
            res    

let memoizedFunc: ('a -> string) when 'a: equality = memoize <| (fun x ->
    string x
)

编译器抱怨值限制：

Value restriction. The value 'memoizedFunc' has been inferred to have generic type    val memoizedFunc : ('_a -> string) when '_a : equality    Either make the arguments to 'memoizedFunc' explicit or, if you do not intend for it to be generic, add a type annotation

如上面的示例代码所示，我已经在memoizedFunc上准确地添加了建议的类型注释，但没有用。另一个建议，即添加参数（eta-conversion），将无法实现我想要的记忆（每次调用该函数都会导致缓存一个新函数）。

我的第一个问题：如何解决这个值限制问题？我可以恢复到更明确的缓存机制，但我不想这样做。

我的第二个问题与记忆函数的另一种定义有关，其中类型参数显式添加到 let 绑定中，如下所示：

let memoizedFunc<'a when 'a: equality> : ('a -> string) when 'a: equality = memoize <| (fun x ->
    ...

即完整的例子变成：

module Sample

open System.Collections.Generic;

let memoize f =
    let cache = Dictionary<_, _>()
    fun x ->
        if cache.ContainsKey(x) then 
            cache.[x]
        else 
            let res = f x
            cache.[x] <- res
            res    

let memoizedFunc<'a when 'a: equality> : ('a -> string) when 'a: equality = memoize <| (fun x ->
    string x
)

现在可以编译，但没有达到我想要的效果：每次我引用 memoizedFunc 时都会创建并记忆一个新函数。

我的第二个问题：如图所示，在 let 绑定中添加类型参数与省略它们相比有什么意义？我没想到这会影响语义，而只是为了帮助类型推断。但似乎并非如此。

任何关于这两个问题的指示或帮助将不胜感激。

非常感谢。

Answer 1

您的 memoize 函数没有任何问题，但是 F#（和整个 .Net）类型系统不允许您做您想做的事。 Dictionary<'T, 'U> 是通用的，但是对于 Dictionary 的每个实例，'T 和 'U 需要是具体类型。您不能拥有一个包含多种不同类型作为键的字典，即使它们都解析为字符串作为值。

解决此问题的方法是，当密钥位于已知集合中时，使用 Interface for when the keys are in an unbounded set (obj can even be used as the supertype of everything) or Discriminated Unions 将所有密钥设为某种通用类型。下面的代码是使用obj作为key的例子。

module Sample =

    open System.Collections.Generic

    let memoize f =
        let cache = Dictionary<_, _>()
        fun x ->
            if cache.ContainsKey(x) then
                cache.[x]
            else
                let res = f x
                cache.[x] <- res
                res

    let memoizedFunc: (obj -> string) =
        memoize (fun x ->
            printfn "Not in cache, getting string of %s" (string x)
            string x)

    memoizedFunc 1
    memoizedFunc "hello"
    memoizedFunc 1

你的第二个问题我不是专家。一般来说，类型注释只是为了帮助作者而不影响语义。在无法编译的代码中，它们有时会更改显示的错误消息。注释可以使使用 when 'a: expr 语法的函数比编译器可能推断出的函数更不通用。当编译器检测到通用代码中的约束时，也需要这些注释。

F# 中通用约束函数的记忆

Memoization of generic constrained functions in F#

f#

memoization