F# Memoization Within a Class

user_4674546 0
Viewed 87

I am struggling to make Memoization work in F# when the function I want to Memoize is a member of a class. The Dictionary appears to be cleared every time - and so nothing is actually memoized, the result is always recomputed. The same code but with the key functions outside of a calls of a class works just fine.

open System
module TestMemo

open System
open System.IO
open System.Collections.Generic

let Memoize f =
    let dict = Dictionary<_, _>()
    fun c ->
        let exists, value = dict.TryGetValue c
        match exists with
        | true -> value
        | _ -> 
            let value = f c
            dict.Add(c, value)
            value

type MyClass() as this = 
    let rec AddToOne(x) = if x <= 1 then 1 else x + AddToOne(x-1)
    let rec AddToOneSkip(x) = if x <= 1 then 1 else x + AddToOneSkip(x-2)
    
    member this.MemoAddToOne = Memoize AddToOne
    member this.MemoAddToOneSkip = Memoize AddToOneSkip

[<EntryPoint>]
let main args = 
    let x = new MyClass()
    
    for i in 1..100000 do
        Console.WriteLine(x.MemoAddToOneSkip(i))

    for i in 1..100000 do
        Console.WriteLine(x.MemoAddToOne(i))
    
    0
memoization f# functional-programming
1 Answers

When you write this:

member this.MemoAddToOne = Memoize AddToOne

That's not a "value", but a property. A property in .NET is a pair of functions (get + set), but there are also read-only properties, which have only "get". And that's what you created here. They're basically functions in disguise.

So every time somebody accesses x.MemoAddToOne, they're basically calling a function, so every time the body is executed anew, thus making a new call to Memoize every time.

To avoid this, create the memoizers once and then return them from the property getter:

let memoAddToOne = Memoize AddToOne
member this.MemoAddToOne = memoAddToOne

Or use a shortcut for the same thing:

member val MemoAddToOne = Memoize AddToOne
user_1802860
Related