Fergus Henderson <[EMAIL PROTECTED]> writes:
> On 07-May-1998, S. Alexander Jacobson <[EMAIL PROTECTED]> wrote:
> > On 07-May-1998, Ralf Hinze <[EMAIL PROTECTED]> wrote:
(in reference to the following code)
> quicksort [] = []
> quicksort (x:xs) = quicksort [y | y <- xs, y<x ] ++ [x] ++ quicksort [y | y <- xs,
>y>=x]
> > > > o it traverses the list twice,
> > > > o it has a space leak (xs is alive until the second traversal is done),
> >
> > Is it necessary that the compiler do this? It strikes me that when the
> > compiler encounters a function that requires multiple comprehensions of
> > the same list, it should be smart enough to consolidate them into a single
> > loop (which would also avoid the space leak). Is my intuition correct
> > here?
>
> This optimization would probably be a win most of the time, so
> yes, ideally compilers would do things like that. Currently however
> those sort of optimizations are past the limits of what most Haskell
> compilers will do.
Watch out...this optimization is invalid. Consider the following
module:
> data Foo = Foo deriving Eq
>
> instance Ord Foo where
> Foo < Foo = False
> Foo <= Foo = True
> Foo > Foo = False
> Foo >= Foo = error "Bad comparison"
>
> quicksort [] = []
> quicksort (x:xs) = quicksort [y | y <- xs, y<x ] ++ [x] ++ quicksort [y | y <- xs,
>y>=x]
>
> result = head (quicksort [Foo, Foo, Foo])
Here, result evaluates to Foo. However, if the compiler had merged
the two list comprehensions, evaluating both "y<x" and "y>=x" for each
element of "xs" on its single pass through "xs", evaluating result
would lead to a "Bad comparison" error.
Carl Witty
[EMAIL PROTECTED]
