Back to Questions
1.0k
views2
comments
Does F# lazy really memoize?
f#

There's a rather old blog post that gleefully demonstrates memoization in F#: [link:weblogs.asp.net]

let lazyMultiply =

lazy

(

let multiply = 4 * 4

printf "This is a side effect"

multiply

)

But then I try something similar, with an argument, and it doesn't memoize:

let f x = lazy (

let ret = "hi " + x

printfn "calling f %s" x

ret

)

The difference here of course is that "multiply" would be evaluated only once regardless of whether or not lazy memoizes, because it's a value and not a function. I don't know what the intent of the blog post was, but it seems wrong.

So, at least with this method, it doesn't look like lazy memoizes -- and that I have to use the cumbersome memoization pattern involving a mutable data structure.

Am I missing something? Is this really the only way to memoize lazy evaluations in F#?

.

I believe that what the blog post is trying to demonstrate is that the lazy value's Force member is memoized; forcing a single lazy value multiple times will only result in the lazy value's definition being executed a single time. I don't think that the blogger was trying to imply that applying "lazy" would memoize functions in general.

Having said that, I don't see what's so "cumbersome" about the traditional memoization pattern:

1
2
3
4
5
6
7
8
9
10
11
12
13

let memoize f =
  let dict = System.Collections.Generic.Dictionary<_,_>()
  fun x ->
    if not (dict.ContainsKey x) then
      dict.[x] <- f x
    dict.[x]


let f = 
  memoize (fun x ->
    let ret = "hi " + x
    printfn "calling f %s" x
    ret)
By on 12/10/2010 7:25 AM ()

Isn't that lazy before it is forced is just a function wrapper around a computation in the first place ?

I think in your case instead of returning lazy from the function you should have regular function with the computation and then

have something like: let susp = lazy (f 4)

so when you call susp.Force()

f 4 is evaluated once, and the result is memoized

By on 12/10/2010 5:24 AM ()

    Topic tags

    IntelliFactory Offices Copyright (c) 2011-2012 IntelliFactory. All rights reserved.
    Home | Products | Consulting | Trainings | Blogs | Jobs | Contact Us | Terms of Use | Privacy Policy | Cookie Policy     		Built with WebSharper