Thanks very much for the help... I will look at this over the next couple of
days. Your code actually addresses a different problem, the one of merging
separates lists of timed events. I do need to write code to do that eventually,
so I will try to understand what you have written here. However, the original
problem concerns visual layout, which actually takes place *after* creating a
merged list. In layout, items do have times associated with them, but also take
up physical space. Different items takes up different amounts of space, and at
any given "time," there may be items on all the staves or just some of them. I
will try to come up with
(1) a more succinct explanation of the problem (with textual graphics as a
visual aid)
(2) a more succinct algorithm.
For example, you are right that I'm mixing concerns. The system layout can
terminate for two reasons: (1) reached the end of the score (2) reached the
right edge of the page. There might be a way to simplify the loop or fold so
that these concerns look more unified.
-Mike
PS a question below:
Heinrich Apfelmus wrote:
Michael Mossey wrote:
Heinrich Apfelmus wrote:
Can you elaborate on what exactly the algorithm is doing? Does it just
emit notes/chords/symbols at given positions or does it also try to
arrange them nicely? And most importantly, "where" does it emit them to,
i.e. what's the resulting data structure?
So far, the problem looks like a basic fold to me.
Here is some Haskell code that explains the problem in
more detail.
[...]
Thanks for the elaboration.
I think the code doesn't separate concerns very well; mixing information
about widths and times, page size and the recursion itself into one big
gnarl.
Also, there is one important issue, namely returning a special value
like -1 as error code in
tryAgain state =
case scoreNextTime score (time state) of
-1 -> indicateNoMoreChunks state
t -> layoutSystem' (setTime state t)
Don't do this, use Maybe instead
tryAgain state = case scoreNextTime score (time state) of
Nothing -> indicateNoMoreChunks state
Just t -> layoutSystem' (state { time = t })
where Nothing indicates failure and Just success.
Back to the gnarl in general, I still don't have a good grasp on the
problem domain, which is key to structuring the algorithm. Therefore,
I'll expand on toy model and you tell me how it differs from the real thing.
The model is this: we are given several lists of notes (f.i. a piano
part and a vocal line) where each note is annotated with the time it is
to be played at. We abstract away the fact that we are dealing with
musical notes and simply consider a list of *events*
type Time = Integer
type Events a = [(Time, a)]
with the invariant that the timestamps are (strictly) increasing:
valid :: Events a -> Bool
valid xs = all $ zipWith (\(t1,_) (t2,_) -> t1 < t2) xs (drop 1 xs)
Now, the toy task is to merge several lists of similar events into one
big list that is ordered by time as well.
merge :: [Events a] -> Events [a]
Since some events may now occur simultaneously, the events of the
results are actually lists of "primitive" events.
One possibility for implementing merge is to start with a function to
merge two event lists
merge2 :: Events [a] -> Events [a] -> Events [a]
merge2 [] ys = ys
merge2 xs [] = xs
merge2 xs@((tx,x):xt) ys@((ty,y):yt) = case compare tx ty of
LT -> (tx,x ) : merge2 xt ys
EQ -> (tx,x++y) : merge2 xt yt
GT -> (ty, y) : merge2 xs yt
and to apply it several times
merge = foldr merge2 [] . map lift
where lift = map $ \(t,x) -> (t,[x])
Another possibility is to simply concatenate everything first and then
sort by time
merge = map (\((t,x):xs) -> (t,x:map snd xs))
. groupBy ((==) `on` fst)
. sortBy (comparing fst)
. concat
The code above can be made more readable by choosing nice names like
time = fst
event = snd
or avoiding pairs altogether and implementing these names as record
fields. Also, the (&&&) combinator from Control.Arrow is very handy.
merge = map (time . head &&& map event)
. groupBy ((==) `on` time)
. sortBy (comparing time)
. concat
I hope this gives you a few ideas to think about. How does this toy
model differ from the real thing?
Regards,
apfelmus
PS: If some parts of my example code give you trouble, it's probably
fastest to ask around on the #haskell IRC channel.
--
http://apfelmus.nfshost.com
_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
_______________________________________________
Haskell-Cafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe
