Re: [Haskell-beginners] laziness and optimization
You should not rely on the compiler to spot such things. As far as I know GHC doesn't do automatic caching (in many cases that would hurt performance, I think). Have a look at http://haskell.org/haskellwiki/ Memoization perhaps. Am 21.03.2009 um 14:02 schrieb Michael Mossey:
I understand a bit about the concept of "lazy evaluation." I think of that as saying an imperative language would always make one evaluation, whereas Haskell might make 0 evaluations. I have another similar situation where an imperative language would make N evaluations of the same expression, and I would like Haskell to make only 1.
This is the situation: the graphical score editor displays "LayoutItems." A LayoutItem can be a single displayed entity, like a round notehead, or it can be composed of several entities.
A common situation in my code is the need to determine the size and shape of a LayoutItem. For a fundamental item, this can be looked up in a table or read from the font properties. For a composite item, some computation is required: the code must determine the positions of each sub-item and compute the bounds of a shape containing all of them.
It's this latter computation, finding the bounds of a composite item, which might come up multiple times. Consider that I ask for the bounds of a composite-composite item (a composite item composed of composite items). It will run the computation associated with each composite sub-item, even though it is very likely I already make that computation when I first constructed and placed that sub- item.
In an imperative language, one might cache values for later lookup. This raises the problem of keeping the cache current to the current state.
So I'm wondering to what extent the haskell compiler recognizes computations it's done before. In a purely functional language this should be pretty easy, right? If it sees the same expression, it knows it will have the same value. That's my understanding, so far.
Thanks, Mike _______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners
Yep.
Michael: Haskell doesn't do miracles. It has a well-defined (however,
very cool) evaluation model, and the compiler in 99.9% realistic cases
optimizes it only by a constant factor. Things can't be much better
than that because it is extremely hard or theoretically impossible
(probably by some kind of Rice's theorem) to guarantee that certain
algorithm-changing optimizations won't hurt.
(Same thing for Prolog: when I didn't know it at all, I thought that
it was a magic allmighty theorem prover; turned out that it also had a
well-defined, however very cool, evaluation model)
So, use the strictly-defined lazy evaluation model to its whole
extent, and build your own memoization :)
2009/3/21 Adrian Neumann
You should not rely on the compiler to spot such things. As far as I know GHC doesn't do automatic caching (in many cases that would hurt performance, I think). Have a look at http://haskell.org/haskellwiki/Memoization perhaps.
Am 21.03.2009 um 14:02 schrieb Michael Mossey:
I understand a bit about the concept of "lazy evaluation." I think of that as saying an imperative language would always make one evaluation, whereas Haskell might make 0 evaluations. I have another similar situation where an imperative language would make N evaluations of the same expression, and I would like Haskell to make only 1.
This is the situation: the graphical score editor displays "LayoutItems." A LayoutItem can be a single displayed entity, like a round notehead, or it can be composed of several entities.
A common situation in my code is the need to determine the size and shape of a LayoutItem. For a fundamental item, this can be looked up in a table or read from the font properties. For a composite item, some computation is required: the code must determine the positions of each sub-item and compute the bounds of a shape containing all of them.
It's this latter computation, finding the bounds of a composite item, which might come up multiple times. Consider that I ask for the bounds of a composite-composite item (a composite item composed of composite items). It will run the computation associated with each composite sub-item, even though it is very likely I already make that computation when I first constructed and placed that sub-item.
In an imperative language, one might cache values for later lookup. This raises the problem of keeping the cache current to the current state.
So I'm wondering to what extent the haskell compiler recognizes computations it's done before. In a purely functional language this should be pretty easy, right? If it sees the same expression, it knows it will have the same value. That's my understanding, so far.
Thanks, Mike _______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
-- Eugene Kirpichov Web IR developer, market.yandex.ru
participants (2)
-
Adrian Neumann -
Eugene Kirpichov