[Haskell-cafe] Haskell and "memoization"

[michael rice]

Thanks all,

OK, so this definition of fib

fib 0 = 1
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

would involve a lot of recomputation for some large n, which memoization would eliminate?

Michael

--- On Wed, 12/16/09, michael rice <nowgate at yahoo.com> wrote:

From: michael rice <nowgate at yahoo.com>
Subject: Re: [Haskell-cafe] Haskell and "memoization"
To: "Daniel Fischer" <daniel.is.fischer at web.de>, "Gregory Crosswhite" <gcross at phys.washington.edu>
Cc: haskell-cafe at haskell.org
Date: Wednesday, December 16, 2009, 12:58 AM

Hi all,

I think this (#3 below) is where I got the idea:

http://en.wikipedia.org/wiki/Lazy_evaluation

Excerpt:

---------------

Lazy evaluation refers to how expressions are evaluated when they are passed as arguments to functions and entails the following three points:[1]

   1. The expression is only evaluated if the result is required by the calling function, called delayed evaluation.[2]
   2. The expression is only evaluated to the extent that is required by the calling function, called Short-circuit evaluation.
   3. the expression is never evaluated more than once, called applicative-order evaluation.[3]

---------------

So, I guess #3 doesn't apply to Haskell, or maybe I just misunderstood the meaning of the statement. I assumed that if f(p) = q (by some
 calculation) then that calculation would be replaced by q so the next time the function was called it could just return q, as occurs in memoization.

Michael



--- On Tue, 12/15/09, Gregory Crosswhite <gcross at phys.washington.edu> wrote:

From: Gregory Crosswhite <gcross at phys.washington.edu>
Subject: Re: [Haskell-cafe] Haskell and "memoization"
To: "Daniel Fischer" <daniel.is.fischer at web.de>
Cc: haskell-cafe at haskell.org
Date: Tuesday, December 15, 2009, 11:47 PM

Hmm, you raise an 
On Dec 15, 2009, at 8:28 PM, Daniel Fischer wrote:

> Am Mittwoch 16 Dezember 2009 05:08:39 schrieb Gregory Crosswhite:
> 
> Not even then, necessarily. And it's not always a good idea.
> 
> f k = [1 .. 20^k]
> 

You raise a really good
 point here.  One can force sharing, as I understand it, by using a let clause:

n =
    let xs = f 20
    in length (xs ++ xs)

If I understand correctly, this should cause xs to be first evaluated, and then cached until the full length is computed, which in this case is obviously undesirable behavior.

Cheers,
Greg

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe at haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe





      
-----Inline Attachment Follows-----

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe at haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe



      
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20091216/8009fb84/attachment.html