caching - F#：尝试记忆成员函数在每次调用时重置缓存？

Question

我正在尝试记忆一个类的成员函数，但是每次（由另一个成员）调用该成员时，它都会创建一个全新的缓存和“记忆”函数。

member x.internal_dec_rates = 
        let cache = new Dictionary< Basis*(DateTime option), float*float>()
        fun (basis:Basis) (tl:DateTime option) ->
            match cache.TryGetValue((basis,tl)) with
            | true, (sgl_mux, sgl_lps) -> (sgl_mux, sgl_lps)
            | _ ->
                let (sgl_mux, sgl_lps) =
                    (* Bunch of stuff *)
                cache.Add((basis,tl),(sgl_mux,sgl_lps))
                sgl_mux,sgl_lps

我使用“真实世界函数式编程”中的清单 10.5 作为模型。我试过使用记忆高阶函数，但没有帮助。上面的清单直接内置了 memoization。

问题是，当我称之为例如

member x.px (basis:Basis) (tl: DateTime option) = 
        let (q,l) = (x.internal_dec_rates basis tl)
        let (q2,l2) = (x.internal_dec_rates basis tl)
        (exp -q)*(1.-l)

执行到 'let cache=...' 行，完全失败了。我放入 (q2,l2) 行以确保它不是范围问题，但似乎不是。

事实上，我使用 Petricek 的代码作为成员函数进行了测试，这似乎有同样的问题：

// Not a member function
let memo1 f =
    let cache = new Dictionary<_,_>()
    (fun x ->
        match cache.TryGetValue(x) with
        | true, v -> v
        | _ -> let v = f x
               cache.Add(x,v)
               v
    )

member x.factorial = memo1(fun y->
    if (y<=0) then 1 else y*x.factorial(y-1))

甚至 x.factorial 的内部递归似乎也为每个级别设置了一个新的“缓存”。

我做错了什么，我怎样才能做到这一点？

score 6 · Accepted Answer

回应您对杰克回答的评论，这不必变得乏味。给定一个 memoize 函数：

let memoize f =
  let cache = Dictionary()
  fun x ->
    match cache.TryGetValue(x) with
    | true, v -> v
    | _ -> 
      let v = f x
      cache.Add(x, v)
      v

将您的每个函数定义为 let-bound 值并从您的方法中返回它们：

type T() as x =
  let internalDecRates = memoize <| fun (basis: Basis, tl: DateTime option) ->
    (* compute result *)
    Unchecked.defaultof<float * float>

  let px = memoize <| fun (basis, tl) ->
    let (q,l) = x.InternalDecRates(basis, tl)
    let (q2,l2) = x.InternalDecRates(basis, tl)
    (exp -q)*(1.-l)

  member x.InternalDecRates = internalDecRates
  member x.Px = px

唯一的“样板”是let绑定和调用memoize.

编辑：正如 kvb 所指出的，在 F# 3.0 中，自动属性允许更简洁的解决方案：

type T() as x =
  member val InternalDecRates = memoize <| fun (basis: Basis, tl: DateTime option) ->
    (* compute result *)
    Unchecked.defaultof<float * float>

  member val Px = memoize <| fun (basis, tl) ->
    let (q,l) = x.InternalDecRates(basis, tl)
    let (q2,l2) = x.InternalDecRates(basis, tl)
    (exp -q)*(1.-l)

score 5 · Accepted Answer

我在这里看到很多很长的答案；简短的回答是

member x.P = code()

定义一个属性，该属性P具有每次访问时运行的getter。您需要将缓存创建移动到类的构造函数中，以便它只运行一次。code()P

score 4 · Accepted Answer

正如其他人已经说过的，这不能仅通过member在 F# 2.0 中定义一个来完成。您需要一个单独的字段（let绑定值）用于缓存或用于记忆的本地函数。

正如 kvb 所提到的，在 F# 3.0 中，您可以使用member valwhich 来执行此操作，该属性是在创建对象时初始化的（并且具有存储结果的自动生成的支持字段）。这是一个完整的示例来演示这一点（它将在 Visual Studio 2012 中工作）：

open System.Collections.Generic

type Test() = 
  /// Property that is initialized when the object is created
  /// and stores a function value 'int -> int'
  member val Foo = 
    // Initialize cache and return a function value
    let cache = Dictionary<int, int>()
    fun arg ->
      match cache.TryGetValue(arg) with
      | true, res -> res
      | false, _ -> 
          let res = arg * arg
          printfn "calculating %d" arg
          cache.Add(arg, res)
          res
    // Part of the property declaration that instructs
    // the compiler to generate getter for the property
    with get

声明的with get部分可以省略，但我将其包含在此处以使示例更清晰（您也可以使用它with get, set来获取可变属性）。现在您可以test.Foo作为函数调用，它会根据需要缓存值

let t = Test()
t.Foo(10)
t.Foo(10)

这种方法的唯一问题是它t.Foo实际上被编译为返回函数的属性（而不是被编译为方法）。当您使用 F# 中的类时，这不是一个大问题，但如果您从 C# 中调用它，则会出现问题（因为 C# 会将成员视为 type 的属性FSharpFunc<int, int>，这很难使用）。

score 2 · Accepted Answer

John 是正确的——您需要将cache字典移动到该类型的私有、let-bound 成员中。

类型成员的编译方式与let模块中的 -bound 值略有不同，这就是行为差异的原因。如果您复制/粘贴x.internal_dec_rates方法的主体并将其分配给let模块中的 -bound 值，那么它应该可以正常工作，因为 F# 编译器会将其编译为一个闭包，该闭包被创建一次，然后分配static readonly给模块。

一些其他的提示，很好的衡量标准：

类型member方法可以使用可选参数——因此如果您愿意，可以稍微简化方法签名。
您可以只创建一次缓存键并重复使用它（这也有助于避免错误）。
您可以通过为元组指定一个名称（例如，）来简化(sgl_mux, sgl_lps)模式匹配代码value，因为无论如何您只是返回整个元组。

这是我对您的代码的看法：

type FooBar () =
    let cache = new Dictionary< Basis*(DateTime option), float*float>()

    member x.internal_dec_rates (basis : Basis, ?tl : DateTime) =
        let key = basis, tl
        match cache.TryGetValue key with
        | true, value -> value
        | _ ->
            // sgl_mux, sgl_lps
            let value =
                (* Bunch of stuff *)

            cache.Add (key, value)
            value

score 1 · Accepted Answer

您需要将字典移到函数调用之外 - 比如

let cache = new Dictionary< Basis*(DateTime option), float*float>()
member x.internal_dec_rates =             
        fun (basis:Basis) (tl:DateTime option) ->
            match cache.TryGetValue((basis,tl)) with
            | true, (sgl_mux, sgl_lps) -> (sgl_mux, sgl_lps)
            | _ ->
                let (sgl_mux, sgl_lps) =
                    (* Bunch of stuff *)
                cache.Add((basis,tl),(sgl_mux,sgl_lps))
                sgl_mux,sgl_lps

这样，缓存在函数调用中持续存在。你memo1有同样的问题。在原始版本中，每次调用函数时都会创建一个新的缓存，这样我们就只有一个缓存，它在函数调用中保持不变。

score 1 · Accepted Answer

除了其他答案，请注意，在 F# 3.0 中，您可以使用自动实现的属性，这些属性将按照您的意愿行事：

member val internal_dec_rates = ...

在这里，右手边只被评估一次，但一切都是独立的。

caching - F#：尝试记忆成员函数在每次调用时重置缓存？

6 回答 6

Related

Reference