Send Beginners mailing list submissions to beginners@haskell.org To subscribe or unsubscribe via the World Wide Web, visit http://www.haskell.org/mailman/listinfo/beginners or, via email, send a message with subject or body 'help' to beginners-requ...@haskell.org
You can reach the person managing the list at beginners-ow...@haskell.org When replying, please edit your Subject line so it is more specific than "Re: Contents of Beginners digest..." Today's Topics: 1. Problem "grouping" a list (Jo?o Paulo Pizani Flor) 2. Re: Problem "grouping" a list (Stephen Tetley) 3. Re: Problem "grouping" a list (Ozgur Akgun) 4. Re: Problem "grouping" a list (Jo?o Paulo Pizani Flor) ---------------------------------------------------------------------- Message: 1 Date: Tue, 23 Nov 2010 15:23:28 -0200 From: Jo?o Paulo Pizani Flor <joaopiz...@gmail.com> Subject: [Haskell-beginners] Problem "grouping" a list To: beginners@haskell.org Message-ID: <aanlktinj2em8cqrfzacanaidkdig4dnon_4g8q5hn...@mail.gmail.com> Content-Type: text/plain; charset="utf-8" Hello dear Haskellers! I've been a user and big fan of Haskell for a while, but only now I'm writing my first "big" project in Haskell (some thousands of lines of code perhaps). It's an interpreter for a programming language, the source code is music! Yes, sheet music! :D OK, so my specific problem goes like this: I have a list of tuples :t myList [ (Float, Integer) ] And I want to "group" this list into a nested list groupAtoms :: [ (Float,Integer) ] -> [ [(Float,Integer)] ] Of course, I want that the concatenation of the groups yield me the original list, i.e, (foldl (++) [] . groupAtoms == id), and the criterion that defines a group is that: "The sum of the first elements in the tuples comprising the list must be greater than or equal to 1.0". That is, given a list of tuples, the boolean predicate deciding whether this list is a PROPER group (True) or TOO SMALL (False) is: \g -> sum (map fst g) >= 1.0 Although the criterion is very clear, I've tried hard until now and couldn't come up with a function for producing the nested list based on this grouping criterion. I am sure that the Haskell Hierarchical Libraries have something to help me, but only now I see I'm still a big noob :P Could someone please help me writing this function? My best regards from Brazil, João Paulo Pizani Flor joaopiz...@gmail.com Federal University of Santa Catarina -------------- next part -------------- An HTML attachment was scrubbed... URL: http://www.haskell.org/pipermail/beginners/attachments/20101123/c97865cf/attachment-0001.html ------------------------------ Message: 2 Date: Tue, 23 Nov 2010 20:25:18 +0000 From: Stephen Tetley <stephen.tet...@gmail.com> Subject: Re: [Haskell-beginners] Problem "grouping" a list Cc: beginners@haskell.org Message-ID: <aanlktikn9w_effqaxokucohnm4=xqelr+jmds0ltc...@mail.gmail.com> Content-Type: text/plain; charset=ISO-8859-1 Are you wanting this function for something like beam grouping - i.e. notes less than a quarter note are grouped together until their values sum to a quarter note? If this is what you want, it can be quite a tough problem - I've done it in concert with bar splitting (two problems!). Personally I'd use direct recursion rather than a left-fold - you have to go from left-to-right however you do it. To do it properly you'll probably find you need to "borrow" durations from the next beam group, this is why I wouldn't use a left fold: For instance if you are splitting to quarter notes - a dotted quarter note with "borrow" an eighth from the next beam group. That said, I'd strongly caution against working with sheet music - it is much more complicated than working with played sound - e.g. MIDI or WAV files. Music type-setting has had 1000 years since Guido d'Arezzo to develop notations with no concession to computer processing. Best wishes Stephen ------------------------------ Message: 3 Date: Tue, 23 Nov 2010 20:36:53 +0000 From: Ozgur Akgun <ozgurak...@gmail.com> Subject: Re: [Haskell-beginners] Problem "grouping" a list To: Jo?o Paulo Pizani Flor <joaopiz...@gmail.com> Cc: beginners@haskell.org Message-ID: <aanlktinwch==1-05rtdhnsmx8ekwhxdpmt2g47u08...@mail.gmail.com> Content-Type: text/plain; charset="utf-8" 2010/11/23 João Paulo Pizani Flor <joaopiz...@gmail.com> > "The sum of the first elements in the tuples comprising the list must be > greater than or equal to 1.0". That is, given a list of tuples, the boolean > predicate deciding whether this list is a PROPER group (True) or TOO SMALL > (False) is: > \g -> sum (map fst g) >= 1.0 > Either I am missing something obvious or this is a weird criterion. The following function satisfies the requirement, if it is satisfiable at all. groupAtoms = return This would be an interesting problem, if you said you were trying to maximise the number of groups returned. -- Ozgur Akgun -------------- next part -------------- An HTML attachment was scrubbed... URL: http://www.haskell.org/pipermail/beginners/attachments/20101123/c8bac2a3/attachment-0001.html ------------------------------ Message: 4 Date: Wed, 24 Nov 2010 09:08:26 -0200 From: Jo?o Paulo Pizani Flor <joaopiz...@gmail.com> Subject: Re: [Haskell-beginners] Problem "grouping" a list To: beginners@haskell.org Message-ID: <aanlktimn1x=azve-aw-emjkwtg4=i-4eveb59k6tm...@mail.gmail.com> Content-Type: text/plain; charset="utf-8" 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... 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. 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! Thanks a lot! João Paulo Pizani Flor joaopiz...@gmail.com Federal University of Santa Catarina 2010/11/23 Daniel Fischer <daniel.is.fisc...@web.de> > On Tuesday 23 November 2010 18:23:28, João Paulo Pizani Flor wrote: > > Hello dear Haskellers! > > > > I've been a user and big fan of Haskell for a while, but only now I'm > > writing my first "big" project in Haskell (some thousands of lines of > > code perhaps). It's an interpreter for a programming language, the > > source code is music! Yes, sheet music! :D > > > > OK, so my specific problem goes like this: I have a list of tuples > > > > :t myList > > > > [ (Float, Integer) ] > > > > And I want to "group" this list into a nested list > > groupAtoms :: [ (Float,Integer) ] -> [ [(Float,Integer)] ] > > > > Of course, I want that the concatenation of the groups yield me the > > original list, i.e, (foldl (++) [] . groupAtoms == id), > > Here, foldr is the better choice. (++) can start delivering its result > before inspecting its second argument, hence > > foldr (++) [] (list1 : list2 : list3 : ...) > = list1 ++ (foldr (++) [] (list2 : list3 : ...)) > = list1 ++ (list2 ++ (foldr (++) [] (list3 : ...))) > > can be consumed as it is constructed, so it can run in constant space, and > it can stop early if not the entire result is needed. And it can deal with > infinite lists. > > The prelude function concat does this. > > foldl on the other hand can't deliver anything before the whole input list > has been traversed, in particular it doesn't terminate on infinite input, > it needs at least O(length result) space and it can't stop early. > Additionally, foldl (++) [] constructs left-nested (++)-applications, which > are bad for performance. > > > and the criterion that defines a group is that: > > "The sum of the first elements in the tuples comprising the list must be > > greater than or equal to 1.0". That is, given a list of tuples, the > > boolean predicate deciding whether this list is a PROPER group (True) or > > TOO SMALL (False) is: > > \g -> sum (map fst g) >= 1.0 > > > > > > Although the criterion is very clear, I've tried hard until now and > > couldn't come up with a function for producing the nested list based on > > this grouping criterion. > > Split the task into two parts. > > 1. collect the first group and the remainder of the list as a pair of lists > 2. cons the first group to what recursion on the remainder delivers > > Very much like the definition of `lines'. > > For your use-case, the condition when a group is complete doesn't only > depend on the list element but also on the previous, concretely the running > sum of the first components. > For a general such function, you need > - the stopping condition > - an accumulation parameter > - an update function for the accumulating parameter > as arguments. > For example (stupid names, sorry) > > > breakAcc :: (b -> Bool) -> (a -> b -> b) -> b -> [a] -> ([a],[a]) > breakAcc _ _ _ [] = ([],[]) > breakAcc cond comb acc xxs@(x:xs) > | cond acc = ([],xxs) > | otherwise = (x:ys,zs) > where > (ys, zs) = breakAcc cond comb (comb x acc) xs > > solves part 1, then > > > groupsAcc :: (b -> Bool) -> (a -> b -> b) -> b -> [a] -> [[a]] > groupsAcc _ _ _ [] = [] > groupsAcc cond comb acc xs = let (g,tl) = breakAcc cond comb acc xs > in g : groupsAcc cond comb acc tl > > gives you part 2, and your particular function is > > > groupAtoms :: [(Float,Integer)] -> [[(Float,Integer)]] > groupAtoms = groupsAcc (>= 1.0) ((+) . fst) 0 > > > Of course the last group need not be proper. > If there are long groups, the above can cause a space leak (as lines had in > GHC < 7), that can be avoided by sacrificing a little non-strictness and > replacing the let (g,tl) = ... in with a > > case ... of > (g,tl) -> g : groupsAcc ... > > or, if you need the non-strictness, with a slightly convoluted method as > used for lines in GHC 7. > > > I am sure that the Haskell Hierarchical > > Libraries have something to help me, but only now I see I'm still a big > > noob :P > > > > Could someone please help me writing this function? > > > > > > My best regards from Brazil, > > > > João Paulo Pizani Flor > > joaopiz...@gmail.com > > Federal University of Santa Catarina > > -------------- next part -------------- An HTML attachment was scrubbed... URL: http://www.haskell.org/pipermail/beginners/attachments/20101124/04d42414/attachment-0001.html ------------------------------ _______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners End of Beginners Digest, Vol 29, Issue 34 *****************************************