Mariano Suarez Alvarez <[EMAIL PROTECTED]> writes:
> 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.
Yes, I think this is sound, but is it an optimization? Consider
> (hd:tl) = qsort [0 .. 100]
I believe that evaluating hd will do enough evaluations that tl will
point to something like:
qsort (
(1 ?: (>= 0)) $
(2 ?: (>= 0)) $
(3 ?: (>= 0)) $
...
(100 ?: (>= 0)) $
[]
)
With
> (hd':tl') = qsort' [0 .. 100]
I believe that evaluating hd' will make tl' point to something like:
qsort' [y | y <- [1, 2, 3, ..., 100], y >= 0]
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. If we're to judge the above two quicksort
implementations on how much data is live during intermediate stages, I
think the original qsort' wins.
Carl Witty
[EMAIL PROTECTED]
