Peter M|ller Neergaard writes:
1) The implementation of list concatenation ++. In the Haskell
report it is stated that ++ in general is an operator on monads.
In the case of lists, ++ works as list concatenation. However,
I cannot find any place describing whether the implementation of
++ is supposed to be better than the straight-forward:
[] ++ ys = ys
(x:xs) ++ ys = x : (xs ++ ys)
See Okasaki, "Purely Functional Data Structures" for a discussion on
catenable list and queues. But keep in mind that you may not need it;
while the running time of this algorithm is O(n), in most contexts you
will be accessing the resulting list from the head anyway. This means
that the cost of the concatenation can be amortized over the list
access, leading to amortized O(1) running time. Even if you don't
access the entire list, lazy evaluation means the unaccessed part of
the list won't be evaluated. Again, Okasaki gives a good summary of
amortized cost in the presence of lazy evaluation, and of methods of
proving amortized cost bounds.
Dave Barton <*>
[EMAIL PROTECTED] )0(
http://www.averstar.com/~dlb
