> Ok, clearly I was wrong about list concatenation, but I think I have now
> figured out what was bothering me about Ralf's objection to the of ++.
>
> The argument that the use of ++ in qsort means too many traversals of the
> list makes sense if ++ is strict (or you are using a non-lazy language),
> but I don't see why the list concatenation needs to happen until you are
> going to traverse the list anyway. Laziness means, as far as I understand
> it, that for example:
>
> > testlaziness =take 5 (map (2+) [1,2..]++[5,6..])
> Doesn't fail (it doesn't).
>
> In other words, you only traverse the list when it is
> necessary. So, the time it takes to traverse is time you were going to
> spend anyway and therefore ++ is effectively a constant time operation
> (without destructive updates!).
>
> -Alex-
>
> PS. I want to thank everybody for all the response to this, it has been
> very educational.
Here is another educational one ;-). You are, of course, right that my
estimation about (++) running's time is sometimes a crude approximation
as Haskell is non-strict. However, one has to be very careful in drawing
conclusions such as `++ is effectively a constant time operation'. Here
is the whole story: In a strict language life is easy ;-), the arguments
to a function are already evaluated so (++) takes time linear in the
length of its first argument.
[] ++ bs = bs
(a : as) ++ bs = a : (as ++ bs)
In Haskell (++) forces it's first argument as to decide which equation
should be applied. Hence the running time is _not_ constant. Consider
slowsort again,
> qsort :: (Ord a) => [a] -> [a]
> qsort [] = []
> qsort (a : as) = qsort [ b | b <- as, b <= a ]
> ++ a : qsort [ b | b <- as, b > a ]
If the pivot element `a' is always the maximal element of the list (as
in `qsort [100, 99 .. 1]') `qsort' yields (essentially) an expression
of the form
(...(([] ++ [a1]) ++ [a2]) ++ ... ) ++ [an]
To access the first element of this `list' n unevaluated calls to (++)
must be reduced: the outermost call to (++) triggers the evaluation of
it's first argument which in turn ... Evaluating the complete list
then takes O(n^2) steps.
Of course, the incremental nature of (++) is sometimes used to good
effect. Take, for example, the queue and deque implementations of
Okasaki.
Cheers, Ralf
