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 Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners