[Haskell-beginners] Appending to a list

[Francesco Bochicchio]

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

<nice explanation on : operator - always useful>

>
> 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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/beginners/attachments/20090208/6396d453/attachment.htm