Problem "grouping" a list
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 joaopizani@gmail.com Federal University of Santa Catarina
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
2010/11/23 João Paulo Pizani Flor
"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
participants (3)
-
João Paulo Pizani Flor -
Ozgur Akgun -
Stephen Tetley