3
votes

I'm trying to memoize a member function of a class, but every time the member is called (by another member) it makes a whole new cache and 'memoized' function.

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

I'm using Listing 10.5 in "Real World Functional Programming" as a model. I've tried using a memoization higher-order function and that doesn't help. The above listing has the memoization built in directly.

The problem is, when I call it e.g.

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)

execution goes to the 'let cache=...' line, defeating the whole point. I put in the (q2,l2) line in order to make sure it wasn't a scope problem, but it doesn't seem to be.

In fact I did a test using Petricek's code as a member function and that seems to have the same issue:

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

Even the internal recursion of x.factorial seems to set up a new 'cache' for each level.

What am I doing wrong, and how can I make this work?

6
You may also wish to consider using ConcurrentDictionary if there is any chance your code will be run in parallel. Plain Dictionary can fail in these circumstances.Kit

6 Answers

6
votes

In response to your comment on Jack's answer, this doesn't have to become tedious. Given a memoize function:

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

Define each of your functions as let-bound values and return them from your methods:

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

The only "boilerplate" is the let binding and call to memoize.

EDIT: As kvb noted, in F# 3.0 auto-properties allow a more concise solution:

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)
5
votes

I see a lot of long answers here; the short answer is that

member x.P = code()

defines a property P which has a getter that runs code() every time P is accessed. You need to move the cache creation into the class's constructor, so that it will only run once.

4
votes

As others already said, this cannot be done just by defining a single member in F# 2.0. You either need a separate field (let bound value) for a cache or for a local function that is memoized.

As mentioned by kvb, in F# 3.0, you can do this using member val which is a property that is initialized when the object is created (and has an automatically generated backing field where the result is stored). Here is a complete sample that demonstrates this (it will work in 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

The with get part of the declaration can be omitted, but I include it here to make the sample clearer (you can also use with get, set to get a mutable property). Now you can call test.Foo as a function and it caches the value as required

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

The only problem with this approach is that t.Foo is actually compiled as a property that returns a function (instead of being compiled as a method). This is not a big problem when you use the class from F#, but it would be a problem if you were calling it from C# (because C# would see the member as a property of type FSharpFunc<int, int>, which is hard to use).

2
votes

John is correct -- you need to move the cache dictionary into a private, let-bound member of the type.

Type members are compiled a bit differently than let-bound values in modules, which is the reason for the difference in behavior. If you copy/paste the body of your x.internal_dec_rates method and assign it to a let-bound value in a module, it should work correctly then, because the F# compiler will compile it as a closure which gets created once and then assigned to a static readonly field of the module.

A couple of other tips, for good measure:

  • Type member methods can use optional parameters -- so you can slightly simplify the method signature if you like.
  • You can create the cache key just once and reuse it (this also helps avoid mistakes).
  • You can simplify the (sgl_mux, sgl_lps) pattern-matching code by just assigning the tuple a name (e.g., value), since you're just returning the whole tuple anyway.

Here's my take on your code:

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
1
votes

You need to move the dictionary outside the function call - like

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

This way the cache persists across the function calls. Your memo1 has the same problem. In the original version, you create a new cache every time you call the function, this way we just have a single cache, which persists across function calls.

1
votes

In addition to the other answers, note that in F# 3.0 you can use automatically implemented properties, which will behave as you want:

member val internal_dec_rates = ...

Here, the right hand side is evaluated only once, but everything is self-contained.