[Haskell-cafe] The values of infinite lists

Claus Reinke claus.reinke at talk21.com
Thu May 25 05:38:12 EDT 2006

>> you don't actually need lazyness. 
> (except if you tried to define >> directly instead of using >>= as the 
> primitive because then the second parameter would be an action directly 
> instead of a continuation)

yes, you'd want >> to be non-strict in its second parameter.

> Thanks! This is *absolutely* the central problem in my understanding since I 
> never know whether I am allowed to assume that evaluation does not happen 
> under a lambda.

well, assumptions like that are on shaky ground in the presence of optimizing
compilers, but you can look at it this way: most functional languages, strict
and non-strict, assume evaluation of functions to weak head normal form,
stopping at the outermost lambda. formally, they probably ought to evaluate
at least a little further, to head normal form (lots of lambdas, then a variable
or an application with a variable in function position), but they don't --
(\x->undefined) and (\x->(\y->undefined)) are distinguishable in Haskell.

so, while an optimizing compiler will try to share expensive computations
in the body instead of reevaluating them every time a lambda is applied,
it is up to the compiler optimization writer to ensure that such evaluation
does not produce different effects than not evaluating under lambdas
(apart from improved resource utilization).
> For example, if I wrote a C function:
> int foo(int x, int y){
>     int z = 24 + 67 + 108 + x;
>     int w = 200 + y;
>     return z + w;
> }
> I would be very disappointed if the compiler didn't evaluate 24 + 67 + 108 + 
> 200 at compilation time, whereas with:
>       foo x y = let
>                          z = 24 + 67 + 108 + x
>                          w = 200 + y
>                      in z + w
>       a = foo 5
> if I understand you correctly I should assume that the expression
>        (24 + 67 + 108 + 5) + (200 + y)
> is left alone until the y argument is supplied to a, rather then a = foo 5 
> causing a to be bound to \y -> 404 + y

as it stands, the compiler can't know the type of y, so it can't know
whether (+) is even associative. if that is known, such optimization
may or may not happen, depending on the implementation. but if
such optimizations do take place, the resulting code must not 
terminate less often or raise more errors than the original version.


More information about the Haskell-Cafe mailing list