Re: quicksort and compiler optimization

[Hans Aberg]

At 18:39 -0300 98/05/09, Mariano Suarez Alvarez wrote:
>The problem is that something like (head (qsort [whatever])) is not strict
>in the whole resulting sorted list, so merging the comprehensions is not a
>win but a loss (a big loss: now we've got bottom!).
>
>If the compiler could prove that the resulting list is needed strictly,
>the merging is ok. This happens in (length (qsort [whatever])). This
>sounds difficult...
>
>The compiler might generate two versions for qsort, one to be used when
>the result is needed strictly, and the other when it is not...

  I am not sure if the following suggestion can be made in Haskell, but I
know that such problems can be solved by treating ``qsort'' as a function
object, with knowledge of qsort.head and qsort.length: One defines
head(foo) = foo.head and length(foo) = foo.length, and then the correct
custom made function can be called. (Notation as in C++.)

  Hans Aberg
                  * Email: Hans Aberg <mailto:[EMAIL PROTECTED]>
                  * Home Page: <http://www.matematik.su.se/~haberg/>
                  * AMS member listing: <http://www.ams.org/cml/>