Re: quicksort and compiler optimization

[Mariano Suarez Alvarez]

On 10 May 1998, Carl R. Witty wrote:

> > > qsort []     = []
> > > qsort (x:xs) = let (a,b) = foldr (\y -> (y ?: (<x) # y ?: (>=x))) ([],[]) xs
> > >                in qsort a ++ [x] ++ qsort b
> > > f # g  = \(x,y) -> (f x,g y)
> > > x ?: p = if p x then (x:) else id
> > > qsort' []     = []
> > > qsort' (x:xs) = qsort' [y | y<-xs, y<x] ++ [x] ++ qsort' [y | y<-xs, y>=x]
> > >
> > > the proof is easy. 
> Yes, I think this is sound, but is it an optimization?  

The paper by Launchbury, Peyton Jones & Gill (which is where I got it
from) introduces it as such... This is very fallacious as an 
argumentation, I know... :)

> This discussion began as a way to keep xs (from the definition of
> qsort' above) from being live in this situation.  The definition of
> qsort above does this--possibly (if xs were not shared elsewhere)
> freeing up some cons cells--but only at the cost of introducing some
> much larger data structures.  Note that all the elements of xs are
> still live in both cases.

I don't think that keeping xs from being alive be possible, at least in
general, because if >= might lead to bottom when < doesn't, one has to
keep all the elements in xs somewhere.  qsort and qsort' are both (at
least) linear in space; different constant factor. The much larger data 
structures needed in the qsort case recall the fact that the list has
already been traversed: we are trading space for time...

One might write

> qsort2 []     = []
> qsort2 (x:xs) = qsort2 a ++ [x] ++ qsort2 b
>   where (a,b) = partition (<x) xs

using partition from the List library. But this is cheating, as this
depends on < and >= being one the negation of the other, which we are not
assuming, as in the T example (I can't think of *one* meaningful example
where < and >= are as in the Ord T instance) 

-- m

-----------------------------------------------------------------------
Mariano Suarez Alvarez                              The introduction of
Departamento de Matematica                       numbers as coordinates
Universidad Nacional de Rosario             [...] is an act of violence
Pellegrini 250                                                  A. Weyl
2000 Rosario - Argentina                                        
e-mail: [EMAIL PROTECTED]
-----------------------------------------------------------------------