Re: quicksort and compiler optimization

[Mariano Suarez Alvarez]

qsort can be rewritten (by the compiler, ideally...) so that the list is
traverse once, without losing any laziness:

> infix 5 #
> infix 6 ?:

Define

> qsort []     = []
> qsort (x:xs) = let (a,b) = foldr (\y -> (y ?: (<x) # y ?: (>=x))) ([],[]) xs
>                in qsort a ++ [x] ++ qsort b

where (#) is cartesian product of functions

> f # g  = \(x,y) -> (f x,g y)

and ?: is a conditional cons

> x ?: p = if p x then (x:) else id

This definition of qsort is equivalent (on reasonable lists, ie finite
with no bottoms inside) to the original

> qsort' []     = []
> qsort' (x:xs) = qsort' [y | y<-xs, y<x] ++ [x] ++ qsort' [y | y<-xs, y>=x]

The proof is easy.

With this definition of qsort, we have no problem evaluating result below:

> data T = T deriving (Eq,Show)

> instance Ord T where
>  T < T        = False
>  T <= T       = True
>  T > T        = False
>  T >= T       = error "Oops!"

> result = head (qsort [T,T,T,T])

qsort could be made a little simpler if one were allowed to assume (I
think one isn't?) that Ord instances satify the usual laws for an (linear)
order, such as < being the negation of >= (the instance for T above
doesnt'). 

The same idea works in general: if E is some expression,

E (foldr f1 b1 xs) (foldr f2 b2 xs)
  = let (a,b) = (foldr f1 b1 xs,foldr f2 b2 xs)
    in E a b
  = let (a,b) = (foldr f1 b1 xs,foldr f2 b2 xs)
    in E a b
  = let (a,b) = foldr (\x -> (f1 x # f2 x)) (b1,b2) xs
    in E a b

This is useful, since usually list traversing functions can be writen 
using foldr. I remember reading about this somewhere...

-- 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]
-----------------------------------------------------------------------