[Haskell-cafe] Newbie Haskell optimization question
Janis Voigtlaender
voigt at tcs.inf.tu-dresden.de
Tue Nov 21 03:10:29 EST 2006
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 at tcs.inf.tu-dresden.de
More information about the Haskell-Cafe
mailing list