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
*****************************************
