[Haskell-cafe] Re: [Haskell-beginners] laziness and optimization

[Eugene Kirpichov]

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 <aneumann at inf.fu-berlin.de>:
> 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 at haskell.org
>> http://www.haskell.org/mailman/listinfo/beginners
>
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
>



-- 
Eugene Kirpichov
Web IR developer, market.yandex.ru