When I previously asked about memoization, I got the impression that memoization is not something that just happens magically in Haskell. Yet, on a Haskell wiki page about Memoization http://www.haskell.org/haskellwiki/Memoization#Memoization_with_recursion, an example given is memoized_fib :: Int -> Integer memoized_fib = (map fib [0 ..] !!) where fib 0 = 0 fib 1 = 1 fib n = memoized_fib (n-2) + memoized_fib (n-1) I guess this works because, for example, I tried "memoized_fib 10000" and the interpreter took three or four seconds to calculate. But every subsequent call to "memoized_fib 10000" returns instantaneously (as does "memoized_fib 10001"). Could someone explain the technical details of why this works? Why is "map fib [0 ..]" not recalculated every time I call memoized_fib?
Have you tried the compiler? On Sun, Jul 21, 2013 at 11:59 PM, Christopher Howard < christopher.howard@frigidcode.com> wrote:
When I previously asked about memoization, I got the impression that memoization is not something that just happens magically in Haskell. Yet, on a Haskell wiki page about Memoizationhttp://www.haskell.org/haskellwiki/Memoization#Memoization_with_recursion, an example given is
memoized_fib :: Int -> Integer memoized_fib = (map fib [0 ..] !!) where fib 0 = 0 fib 1 = 1 fib n = memoized_fib (n-2) + memoized_fib (n-1)
I guess this works because, for example, I tried "memoized_fib 10000" and the interpreter took three or four seconds to calculate. But every subsequent call to "memoized_fib 10000" returns instantaneously (as does "memoized_fib 10001").
Could someone explain the technical details of why this works? Why is "map fib [0 ..]" not recalculated every time I call memoized_fib?
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
-- -- Regards, KC
memoized_fib :: Int -> Integer memoized_fib = (map fib [0 ..] !!) where fib 0 = 0 fib 1 = 1 fib n = memoized_fib (n-2) + memoized_fib (n-1)
[.. snipped ..]
Could someone explain the technical details of why this works? Why is "map fib [0 ..]" not recalculated every time I call memoized_fib?
A binding is memoized if, ignoring everything after the equals sign, it looks like a constant. In other words, these are memoized: x = 2 Just x = blah (x, y) = blah f = \x -> x + 1 -- f = ... and these are not: f x = x + 1 f (Just x, y) = x + y If you remove the right-hand side of memoized_fib, you get: memoized_fib = ... This looks like a constant. So the value (map fib [0..] !!) is memoized. If you change that line to memoized_fib x = map fib [0..] !! x GHC no longer memoizes it, and it runs much more slowly. -- Chris Wong, fixpoint conjurer e: lambda.fairy@gmail.com w: http://lfairy.github.io/
On 07/21/2013 11:52 PM, Chris Wong wrote:
[.. snipped ..]
A binding is memoized if, ignoring everything after the equals sign, it looks like a constant.
In other words, these are memoized:
x = 2
Just x = blah
(x, y) = blah
f = \x -> x + 1 -- f = ...
and these are not:
f x = x + 1
f (Just x, y) = x + y
If you remove the right-hand side of memoized_fib, you get:
memoized_fib = ...
This looks like a constant. So the value (map fib [0..] !!) is memoized.
If you change that line to
memoized_fib x = map fib [0..] !! x
GHC no longer memoizes it, and it runs much more slowly.
-- Chris Wong, fixpoint conjurer e: lambda.fairy@gmail.com w: http://lfairy.github.io/
Thanks. That's very helpful to know. Yet, it seems rather strange and arbitrary that "f x = ..." and "f = \x -> ..." would be treated in such a dramatically different manner.
On Mon, Jul 22, 2013 at 12:02:54AM -0800, Christopher Howard wrote:
A binding is memoized if, ignoring everything after the equals sign, it looks like a constant. [...] Thanks. That's very helpful to know. Yet, it seems rather strange and arbitrary that "f x = ..." and "f = \x -> ..." would be treated in such a dramatically different manner.
This is actually rather subtle, and it's to do with desugaring of pattern matching and where. f x = expression s x where s = subexpression desugars to f = \x -> (let s = subexpression in expression s x) This is not the same as f = expression s where s = subexpression which desugars to f = let s = subexpression in (expression s) which I think is the same as f = let s = subexpression in (\x -> expression s x) In the first case a new thunk for s is created each time an argument is applied to f. In the second case the same thunk for s exists for all invocations of f. This is nothing to do with explicit memoization by the compiler, but is simply the operational semantics of lazy evaluation in terms of thunks. (I think I got this all right, and if not I hope someone will chime in with a correction. I spent some time trying to grasp this a few months ago, but as I said it's subtle, at least to someone like me who hasn't studied lambda calculus in depth!) Tom
On Mon, Jul 22, 2013 at 07:52:06PM +1200, Chris Wong wrote:
A binding is memoized if, ignoring everything after the equals sign, it looks like a constant.
In other words, these are memoized: [...] f = \x -> x + 1 [...] and these are not:
f x = x + 1
In what sense is the former memoised? I'm not aware of any difference between these two definitions. Tom
in this case, neither of them is memoized. because they don't have any data
in expressions.
"memoized" is for constants who have data structure in its expression
2013/7/22 Tom Ellis
On Mon, Jul 22, 2013 at 07:52:06PM +1200, Chris Wong wrote:
A binding is memoized if, ignoring everything after the equals sign, it looks like a constant.
In other words, these are memoized: [...] f = \x -> x + 1 [...] and these are not:
f x = x + 1
In what sense is the former memoised? I'm not aware of any difference between these two definitions.
Tom
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
On 22.07.2013 09:52, Chris Wong wrote:
memoized_fib :: Int -> Integer memoized_fib = (map fib [0 ..] !!) where fib 0 = 0 fib 1 = 1 fib n = memoized_fib (n-2) + memoized_fib (n-1)
[.. snipped ..]
Could someone explain the technical details of why this works? Why is "map fib [0 ..]" not recalculated every time I call memoized_fib?
A binding is memoized if, ignoring everything after the equals sign, it looks like a constant.
In other words, these are memoized:
x = 2
Just x = blah
(x, y) = blah
f = \x -> x + 1 -- f = ...
and these are not:
f x = x + 1
f (Just x, y) = x + y
If you remove the right-hand side of memoized_fib, you get:
memoized_fib = ...
This looks like a constant. So the value (map fib [0..] !!) is memoized.
If you change that line to
memoized_fib x = map fib [0..] !! x
GHC no longer memoizes it, and it runs much more slowly.
True, but the essential thing to be memoized is not memoized_fib, which is a function, but the subexpression map fib [0..] which is an infinite list, i.e., a value. The rule must be like "in let x = e if e is purely applicative, then its subexpressions are memoized." For instance, the following is also not memoizing: fib3 :: Int -> Integer fib3 = \ x -> map fib [0 ..] !! x where fib 0 = 0 fib 1 = 1 fib n = fib3 (n-2) + fib3 (n-1) In general, I would not trust such compiler magic, but just let-bind anything I want memoized myself: memoized_fib :: Int -> Integer memoized_fib x = fibs !! x where fibs = map fib [0..] -- lazily computed infinite list fib 0 = 0 fib 1 = 1 fib n = memoized_fib (n-2) + memoized_fib (n-1) The eta-expansions do not matter. Cheers, Andreas -- Andreas Abel <>< Du bist der geliebte Mensch. Theoretical Computer Science, University of Munich Oettingenstr. 67, D-80538 Munich, GERMANY andreas.abel@ifi.lmu.de http://www2.tcs.ifi.lmu.de/~abel/
On 07/22/2013 06:16 AM, Andreas Abel wrote:
On 22.07.2013 09:52, Chris Wong wrote:
True, but the essential thing to be memoized is not memoized_fib, which is a function, but the subexpression
map fib [0..]
which is an infinite list, i.e., a value.
The rule must be like "in
let x = e
if e is purely applicative, then its subexpressions are memoized." For instance, the following is also not memoizing:
fib3 :: Int -> Integer fib3 = \ x -> map fib [0 ..] !! x where fib 0 = 0 fib 1 = 1 fib n = fib3 (n-2) + fib3 (n-1)
In general, I would not trust such compiler magic, but just let-bind anything I want memoized myself:
memoized_fib :: Int -> Integer memoized_fib x = fibs !! x where fibs = map fib [0..] -- lazily computed infinite list fib 0 = 0 fib 1 = 1 fib n = memoized_fib (n-2) + memoized_fib (n-1)
The eta-expansions do not matter.
Cheers, Andreas
Is this behavior codified somewhere? (I can't seem to find it in the GHC user guide.) The memoize package from hackage, interestingly enough, states that "[Our memoization technique] relies on implementation assumptions that, while not guaranteed by the semantics of Haskell, appear to be true."
On Mon, Jul 22, 2013 at 04:16:19PM +0200, Andreas Abel wrote:
In general, I would not trust such compiler magic, but just let-bind anything I want memoized myself:
memoized_fib :: Int -> Integer memoized_fib x = fibs !! x where fibs = map fib [0..] -- lazily computed infinite list fib 0 = 0 fib 1 = 1 fib n = memoized_fib (n-2) + memoized_fib (n-1)
The eta-expansions do not matter.
But this is *not* memoized (run it and see!). The "eta-expansions" do indeed matter (although I don't think they are truly eta-expasions because of the desugaring of the where to a let). What matters is not the let binding, but where the let binding occurs in relation to the lambda. There's no compiler magic here, just operational semantics. Tom
Sorry I screwed up. The following is indeed memoizing: fib5 :: Int -> Integer fib5 = \ x -> fibs !! x where fibs = map fib [0 ..] fib 0 = 0 fib 1 = 1 fib n = fib5 (n-2) + fib5 (n-1) Here, the eta-expansion does not matter. But as you say, memoized_fib below is not memoizing, since x is in scope in the where clauses, even though they do not mention it. Thus, for each x we get "new" definitions of fibs and fib. Yet, this is only true for -O0. For -O1 and greater, ghc seems to see that x is not mentioned in the where clauses and apparently lifts them out. Thus, for -O1.. memoized_fib is also memoizing. (I ran it, this time ;-) !) Cheers, Andreas On 22.07.13 11:43 PM, Tom Ellis wrote:
On Mon, Jul 22, 2013 at 04:16:19PM +0200, Andreas Abel wrote:
In general, I would not trust such compiler magic, but just let-bind anything I want memoized myself:
memoized_fib :: Int -> Integer memoized_fib x = fibs !! x where fibs = map fib [0..] -- lazily computed infinite list fib 0 = 0 fib 1 = 1 fib n = memoized_fib (n-2) + memoized_fib (n-1)
The eta-expansions do not matter.
I meant to write "Then, eta-expansions do not matter." (In general, they do matter.)
But this is *not* memoized (run it and see!). The "eta-expansions" do indeed matter (although I don't think they are truly eta-expasions because of the desugaring of the where to a let).
What matters is not the let binding, but where the let binding occurs in relation to the lambda. There's no compiler magic here, just operational semantics.
Tom
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
-- Andreas Abel <>< Du bist der geliebte Mensch. Theoretical Computer Science, University of Munich Oettingenstr. 67, D-80538 Munich, GERMANY andreas.abel@ifi.lmu.de http://www2.tcs.ifi.lmu.de/~abel/
On Wed, Jul 24, 2013 at 10:06:59AM +0200, Andreas Abel wrote:
For -O1 and greater, ghc seems to see that x is not mentioned in the where clauses and apparently lifts them out. Thus, for -O1.. memoized_fib is also memoizing. (I ran it, this time ;-) !)
Right, I believe this is the "full laziness transformation" I mentioned before http://foldoc.org/full+laziness http://www.haskell.org/pipermail/haskell-cafe/2013-February/105201.html Tom
participants (6)
-
14875 -
Andreas Abel -
Chris Wong -
Christopher Howard -
KC -
Tom Ellis