Re: quicksort and compiler optimization

[Hans Aberg]

At 20:21 +1000 98/05/08, Fergus Henderson wrote:
>On 07-May-1998, S. Alexander Jacobson <[EMAIL PROTECTED]> wrote:
>> On 07-May-1998, Ralf Hinze <[EMAIL PROTECTED]> wrote:
>> > > o it uses (++) to catenate the results of the recursive calls (note that
>> > >   (++) takes time proportional to the length of its first argument).
>>
>> This also seems wierd.  Concatenation is a frequent enough operation on
>> lists.  Give such frequency, shouldn't the internal representation of a
>> list include a pointer to its last element just to ensure that
>> concatenation is constant time?
>
>That sort of concatenation is destructive; you can't do that if
>there are still references to the original list.
>Current Haskell compilers don't do destructive update optimization.

  Would not having destructive or "mutative" updates counter the idea of
Haskell being a purely functional language? Mutative sorting is faster than
functional sorting, but does not fit into the idea of a functional language.

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