Slavomir Kaslev wrote:
... g xs = xs ++ g (drop (length xs `div` 2) xs) ...
Now I am thinking of doing some language level optimizations.
As a starter, the argument of g in the above right-hand side traverses xs twice, once to compute the length, then to drop an appropriate number of elements (so actually traverses xs once and a half times). The fullowing funny function could be used instead: h (_:_:xs) (_:ys) = h xs ys h _ ys = ys Then "h xs xs" is the same as "drop (length xs `div` 2) xs". It also kind of traverses xs once and a half times, but in one go. It might also be better in terms of space consumption behavior, because elements in the first half of xs can be reclaimed earlier than in the "drop (length xs `div` 2) xs" case, where the full list xs needs to be kept around until its length is computed and divided by two. A nice exercise: try to provide a function h' in a similar style as above, but in the same traversal computing also the "xs ++" part of the above right-hand side for g, i.e., "h' xs xs" gives "xs ++ g (drop (length xs `div` 2) xs)" without a third traversal of xs being necessary. Have fun, Janis. -- Dr. Janis Voigtlaender http://wwwtcs.inf.tu-dresden.de/~voigt/ mailto:voigt@tcs.inf.tu-dresden.de