I feel that there is something that I don't understand completely: I have been told that Haskell does not memoize function call, e.g.
slowFib 50 will run just as slowly each time it is called. However, I have read that Haskell has call-by-need semantics, which were described as "lazy evaluation with memoization"
I understand that
fib50 = slowFib 50 will take a while to run the first time but be instant each subsequent call; does this count as memoization?
(I'm trying to understand "Purely Functional Data Structures", hence this question) -- Alex R
On 9/15/10, Alex Rozenshteyn
I feel that there is something that I don't understand completely: I have been told that Haskell does not memoize function call, e.g.
slowFib 50 will run just as slowly each time it is called. However, I have read that Haskell has call-by-need semantics, which were described as "lazy evaluation with memoization"
I understand that
fib50 = slowFib 50 will take a while to run the first time but be instant each subsequent call; does this count as memoization?
Hi, Alex -- Haskell's informal semantics dictate that if we evaluate the expression: let fib50 = slowFib 50 in fib50 + fib50 then the expression (slowFib 50) will be evaluated only once, not twice, because it has a name. On the other hand, if you wrote: let fib50 = slowFib 50 in fib50 + (slowFib 50) then (slowFib 50) would be evaluated twice, because there's no principle requiring the compiler to notice that (slowFib 50) is the same expression as the one bound to fib50. An optimization called "full laziness" can accomplish the kind of stronger memoization you were suggesting in some cases, but GHC doesn't do it consistently, as it can make performance worse. Cheers, Tim -- Tim Chevalier * http://cs.pdx.edu/~tjc * Often in error, never in doubt "Both of them are to world religions what JavaScript is to programming languages." -- Juli Mallett, on Satanism and Wicca
On Wednesday 15 September 2010 22:38:48, Tim Chevalier wrote:
On the other hand, if you wrote:
let fib50 = slowFib 50 in fib50 + (slowFib 50)
then (slowFib 50) would be evaluated twice, because there's no principle requiring the compiler to notice that (slowFib 50) is the same expression as the one bound to fib50.
If you compile your module with ghc -O[2], ghc does notice, whether you give it a name once or not - without optimisations, it doesn't, however. And if the two expressions appear far enough apart, it will probably not notice with optimisations either. The upshot is, if you don't name an expression, the compiler *might* notice repeated use and share it, but you'd better not rely on it. If you want an expression to be shared, name it - then a decent implementation will share it.
Hi Alex,
In Haskell, data structures cache, while functions do not.
"Memoization" is conversion of functions into data structures (and then
trivially re-wrapping as functions) so as to exploit the caching property of
data structures to get caching functions.
- Conal
On Wed, Sep 15, 2010 at 11:03 AM, Alex Rozenshteyn
I feel that there is something that I don't understand completely: I have been told that Haskell does not memoize function call, e.g.
slowFib 50 will run just as slowly each time it is called. However, I have read that Haskell has call-by-need semantics, which were described as "lazy evaluation with memoization"
I understand that
fib50 = slowFib 50 will take a while to run the first time but be instant each subsequent call; does this count as memoization?
(I'm trying to understand "Purely Functional Data Structures", hence this question)
-- Alex R
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
On 9/15/10 10:39 PM, Conal Elliott wrote:
Hi Alex,
In Haskell, data structures cache, while functions do not.
Exactly. What this means is that when you call (slowFib 50) Haskell does not alter slowFib in any way to track that it maps 50 to $whatever; however, it does track that that particular expression instance evaluates to $whatever. This is why, when you define fib50=(slowFib 50) it only needs to compute $whatever the first time the value of fib50 is required. After the first evaluation it's the same as if we had defined fib50=$whatever. So, the function being memoized is the evaluation function of Haskell itself, not any of the functions _in_ the language. There are various libraries for memoizing functions in Haskell, they're just not part of the language definition. -- Live well, ~wren
Alex Rozenshteyn
I understand that
fib50 = slowFib 50
will take a while to run the first time but be instant each subsequent call; does this count as memoization?
I didn't see anybody else answering this in so many words, but I'd say no, since you only name one particular value. Memoization of slowFib would mean to provide a replacement for the *function* that remembers previous answers. Try e.g. these in GHCi (import (i.e. :m +) Data.Array for memoFib): slowFib 0 = 1; slowFib 1 = 1; slowFib x = slowFib (x-1) + slowFib (x-2) memoFib x = a!x where a = listArray (0,n) (1:1:[ a!(x-1)+a!(x-2) | x<-[2..99]]) -k -- If I haven't seen further, it is by standing in the footprints of giants
Alex, Maybe this pdf can enlighten you a little bit about memoization and lazy evaluation in Haskell => http://www.cs.uu.nl/wiki/pub/USCS2010/CourseMaterials/A5-memo-slides-english... Cheers. Roman.- I feel that there is something that I don't understand completely: I have
been told that Haskell does not memoize function call, e.g.
slowFib 50
will run just as slowly each time it is called. However, I have read that
Haskell has call-by-need semantics, which were described as "lazy evaluation with memoization"
I understand that
fib50 = slowFib 50
will take a while to run the first time but be instant each subsequent call;
does this count as memoization?
(I'm trying to understand "Purely Functional Data Structures", hence this question)
-- Alex R
Alex Rozenshteyn schrieb:
slowFib 50 will run just as slowly each time it is called. However, I have read
I feel that there is something that I don't understand completely: I have been told that Haskell does not memoize function call, e.g. that Haskell has call-by-need semantics, which were described as "lazy evaluation with memoization"
participants (8)
-
Alex Rozenshteyn -
Conal Elliott -
Daniel Fischer -
Henning Thielemann -
Ketil Malde -
Román González -
Tim Chevalier -
wren ng thornton