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 <[email protected]> wrote: From: michael rice <[email protected]> Subject: Re: [Haskell-cafe] Haskell and "memoization" To: "Daniel Fischer" <[email protected]>, "Gregory Crosswhite" <[email protected]> Cc: [email protected] 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 <[email protected]> wrote: From: Gregory Crosswhite <[email protected]> Subject: Re: [Haskell-cafe] Haskell and "memoization" To: "Daniel Fischer" <[email protected]> Cc: [email protected] 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 [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe -----Inline Attachment Follows----- _______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
_______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
