2009/2/7 Cory Knapp <thestonetable@gmail.com>

Does that help, or did I miss the point?

Ok, I'll try to be more clear with an example: the following function - which surely can be written in better way - takes a list and a predicate and builds two lists. a list of lists of consecutive elements that satisfy the predicate and a list of separators, i.e. of elements that does not satisfy the predicate.

That is: groups odd [1,3,2,5,9,6] ->   [[1,3],[5,9]], [2,6]
The function uses another function, groupWhile, which works like takeWhile but returns also the rest of the list.

Now, from the way the function works, it shoud build the two result lists by appending new elements to them.
But, as you said, appending is expensive in haskell, so instead I build the lists using (:), which gives me the list
in reverse order, and then I use the 'final step' of the function - the base case of the recursion - to reverse the
result. If I understand lazyness, this should be a low-cost operation because it does not actual build a reversed
list, but only make the list to be 'consumed' from the tail.

Now, this trick is not mine: I read it somewhere on internet (I can'tremember where), so I was asking if it is classified among the 'neat tricks' or among the 'ugly hacks' :-)

Here is the code I was referring to:

groups :: (a->Bool)-> [a] -> ([[a]],[a])
groups f lst = groups_ f ([],[]) lst where
    groups_ f (gs,seps) [] = (reverse gs, reverse seps)
    groups_ f (gs,seps) [a] = if (f a)
                              then ( reverse ( [a]:gs), reverse seps )
                              else ( reverse gs , reverse (a:seps) )
    groups_ f (gs, seps) lst = groups_ f (g:gs, r:seps) est
        where
          (g, (r:est)) = groupWhile f lst

Ciao
-------
FB