<div>Thank you all for the helpful responses! The solution from Daniel Fischer worked like a charm, the solution from Aai kinda worked, but I can't use because I don't want to modify the order of the elements in the list...</div>
<div><br></div><div>And yes, my "criterion" was a bit ill-defined, so the very clever function from Ozgur satisfied it :P The real goal is to maximize the number of groups though.</div><div><br></div><div>I'll test the solutions more hardly today and try to make the functions from Daniel even more clearer and elegant. I post the results back here!</div>
<div><br></div><div><br></div><div>Thanks a lot!</div><br clear="all">João Paulo Pizani Flor<div><a href="mailto:joaopizani@gmail.com" target="_blank">joaopizani@gmail.com</a></div><div>Federal University of Santa Catarina</div>
<br><br><div class="gmail_quote">2010/11/23 Daniel Fischer <span dir="ltr"><<a href="mailto:daniel.is.fischer@web.de">daniel.is.fischer@web.de</a>></span><br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
<div class="im">On Tuesday 23 November 2010 18:23:28, João Paulo Pizani Flor wrote:<br>
> Hello dear Haskellers!<br>
><br>
> I've been a user and big fan of Haskell for a while, but only now I'm<br>
> writing my first "big" project in Haskell (some thousands of lines of<br>
> code perhaps). It's an interpreter for a programming language, the<br>
> source code is music! Yes, sheet music! :D<br>
><br>
> OK, so my specific problem goes like this: I have a list of tuples<br>
><br>
> :t myList<br>
><br>
> [ (Float, Integer) ]<br>
><br>
> And I want to "group" this list into a nested list<br>
> groupAtoms :: [ (Float,Integer) ] -> [ [(Float,Integer)] ]<br>
><br>
> Of course, I want that the concatenation of the groups yield me the<br>
> original list, i.e, (foldl (++) [] . groupAtoms == id),<br>
<br>
</div>Here, foldr is the better choice. (++) can start delivering its result<br>
before inspecting its second argument, hence<br>
<br>
foldr (++) [] (list1 : list2 : list3 : ...)<br>
= list1 ++ (foldr (++) [] (list2 : list3 : ...))<br>
= list1 ++ (list2 ++ (foldr (++) [] (list3 : ...)))<br>
<br>
can be consumed as it is constructed, so it can run in constant space, and<br>
it can stop early if not the entire result is needed. And it can deal with<br>
infinite lists.<br>
<br>
The prelude function concat does this.<br>
<br>
foldl on the other hand can't deliver anything before the whole input list<br>
has been traversed, in particular it doesn't terminate on infinite input,<br>
it needs at least O(length result) space and it can't stop early.<br>
Additionally, foldl (++) [] constructs left-nested (++)-applications, which<br>
are bad for performance.<br>
<div class="im"><br>
> and the criterion that defines a group is that:<br>
> "The sum of the first elements in the tuples comprising the list must be<br>
> greater than or equal to 1.0". That is, given a list of tuples, the<br>
> boolean predicate deciding whether this list is a PROPER group (True) or<br>
> TOO SMALL (False) is:<br>
> \g -> sum (map fst g) >= 1.0<br>
><br>
><br>
> Although the criterion is very clear, I've tried hard until now and<br>
> couldn't come up with a function for producing the nested list based on<br>
> this grouping criterion.<br>
<br>
</div>Split the task into two parts.<br>
<br>
1. collect the first group and the remainder of the list as a pair of lists<br>
2. cons the first group to what recursion on the remainder delivers<br>
<br>
Very much like the definition of `lines'.<br>
<br>
For your use-case, the condition when a group is complete doesn't only<br>
depend on the list element but also on the previous, concretely the running<br>
sum of the first components.<br>
For a general such function, you need<br>
- the stopping condition<br>
- an accumulation parameter<br>
- an update function for the accumulating parameter<br>
as arguments.<br>
For example (stupid names, sorry)<br>
<br>
<br>
breakAcc :: (b -> Bool) -> (a -> b -> b) -> b -> [a] -> ([a],[a])<br>
breakAcc _ _ _ [] = ([],[])<br>
breakAcc cond comb acc xxs@(x:xs)<br>
| cond acc = ([],xxs)<br>
| otherwise = (x:ys,zs)<br>
where<br>
(ys, zs) = breakAcc cond comb (comb x acc) xs<br>
<br>
solves part 1, then<br>
<br>
<br>
groupsAcc :: (b -> Bool) -> (a -> b -> b) -> b -> [a] -> [[a]]<br>
groupsAcc _ _ _ [] = []<br>
groupsAcc cond comb acc xs = let (g,tl) = breakAcc cond comb acc xs<br>
in g : groupsAcc cond comb acc tl<br>
<br>
gives you part 2, and your particular function is<br>
<div class="im"><br>
<br>
groupAtoms :: [(Float,Integer)] -> [[(Float,Integer)]]<br>
</div>groupAtoms = groupsAcc (>= 1.0) ((+) . fst) 0<br>
<br>
<br>
Of course the last group need not be proper.<br>
If there are long groups, the above can cause a space leak (as lines had in<br>
GHC < 7), that can be avoided by sacrificing a little non-strictness and<br>
replacing the let (g,tl) = ... in with a<br>
<br>
case ... of<br>
(g,tl) -> g : groupsAcc ...<br>
<br>
or, if you need the non-strictness, with a slightly convoluted method as<br>
used for lines in GHC 7.<br>
<div><div></div><div class="h5"><br>
> I am sure that the Haskell Hierarchical<br>
> Libraries have something to help me, but only now I see I'm still a big<br>
> noob :P<br>
><br>
> Could someone please help me writing this function?<br>
><br>
><br>
> My best regards from Brazil,<br>
><br>
> João Paulo Pizani Flor<br>
> <a href="mailto:joaopizani@gmail.com">joaopizani@gmail.com</a><br>
> Federal University of Santa Catarina<br>
<br>
</div></div></blockquote></div><br>