[Haskell-cafe] Newbie Haskell optimization question

[Janis Voigtlaender]

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