<table cellspacing="0" cellpadding="0" border="0" ><tr><td valign="top" style="font: inherit;">Thanks all,<br><br>OK, so this definition of fib<br><br>fib 0 = 1<br>fib 1 = 1<br>fib n = fib (n-1) + fib (n-2)<br><br>would involve a lot of recomputation for some large n, which memoization would eliminate?<br><br>Michael<br><br>--- On <b>Wed, 12/16/09, michael rice <i><nowgate@yahoo.com></i></b> wrote:<br><blockquote style="border-left: 2px solid rgb(16, 16, 255); margin-left: 5px; padding-left: 5px;"><br>From: michael rice <nowgate@yahoo.com><br>Subject: Re: [Haskell-cafe] Haskell and "memoization"<br>To: "Daniel Fischer" <daniel.is.fischer@web.de>, "Gregory Crosswhite" <gcross@phys.washington.edu><br>Cc: haskell-cafe@haskell.org<br>Date: Wednesday, December 16, 2009, 12:58 AM<br><br><div id="yiv1770129874"><table border="0" cellpadding="0" cellspacing="0"><tbody><tr><td style="font-family: inherit; font-style: inherit; font-variant:
inherit; font-weight: inherit; font-size: inherit; line-height: inherit; font-size-adjust: inherit; font-stretch: inherit; -x-system-font: none;" valign="top">Hi all,<br><br>I think this (#3 below) is where I got the idea:<br><br>http://en.wikipedia.org/wiki/Lazy_evaluation<br><br>Excerpt:<br><br>---------------<br><br>Lazy evaluation refers to how expressions are evaluated when they are passed as arguments to functions and entails the following three points:[1]<br><br> 1. The expression is only evaluated if the result is required by the calling function, called delayed evaluation.[2]<br> 2. The expression is only evaluated to the extent that is required by the calling function, called Short-circuit evaluation.<br> 3. the expression is never evaluated more than once, called applicative-order evaluation.[3]<br><br>---------------<br><br>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.<br><br>Michael<br><br><br><br>--- On <b>Tue, 12/15/09, Gregory Crosswhite <i><gcross@phys.washington.edu></i></b> wrote:<br><blockquote style="border-left: 2px solid rgb(16, 16, 255); margin-left: 5px; padding-left: 5px;"><br>From: Gregory Crosswhite <gcross@phys.washington.edu><br>Subject: Re: [Haskell-cafe] Haskell and "memoization"<br>To: "Daniel Fischer" <daniel.is.fischer@web.de><br>Cc: haskell-cafe@haskell.org<br>Date: Tuesday, December 15, 2009, 11:47 PM<br><br><div class="plainMail">Hmm, you raise an <br>On Dec 15, 2009, at 8:28 PM, Daniel Fischer wrote:<br><br>> Am Mittwoch 16 Dezember 2009 05:08:39 schrieb Gregory Crosswhite:<br>> <br>> Not even then, necessarily. And it's not always a good idea.<br>> <br>> f k = [1 .. 20^k]<br>> <br><br>You raise a really good
point here. One can force sharing, as I understand it, by using a let clause:<br><br>n =<br> let xs = f 20<br> in length (xs ++ xs)<br><br>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.<br><br>Cheers,<br>Greg<br><br>_______________________________________________<br>Haskell-Cafe mailing list<br><a rel="nofollow">Haskell-Cafe@haskell.org</a><br><a rel="nofollow" target="_blank" href="http://www.haskell.org/mailman/listinfo/haskell-cafe">http://www.haskell.org/mailman/listinfo/haskell-cafe</a><br></div></blockquote></td></tr></tbody></table><br>
</div><br>-----Inline Attachment Follows-----<br><br><div class="plainMail">_______________________________________________<br>Haskell-Cafe mailing list<br><a ymailto="mailto:Haskell-Cafe@haskell.org" href="/mc/compose?to=Haskell-Cafe@haskell.org">Haskell-Cafe@haskell.org</a><br><a href="http://www.haskell.org/mailman/listinfo/haskell-cafe" target="_blank">http://www.haskell.org/mailman/listinfo/haskell-cafe</a><br></div></blockquote></td></tr></table><br>