[Haskell-cafe] music-related problem

[Michael Mossey]

Wondering if I could get some suggestions for coding this problem.

A musical document (or "score") consists primarily of a list of measures. A 
measure consists primarily of lists of "items". We'll consider only one 
kind of item: a note. Items have a location within the measure. A note's
location indicates both where it goes on the page (i.e. a visual 
representation of the score) and what moment in time it begins sounding 
(i.e. rendering the score in sound). My concern here is sound.

data Doc = [Measure]

data Loc = ... (represents a location within the musical
                 document including measure number)


data Measure = Measure [(Loc,Item)]
   -- In the Meausre, we can assume (Loc,Item) are in
   --  ascending order


Notes also have an end, when indicates when in time they stop
sounding. See the 'end' field below. Also note the 'soundedEnd'
  'tieStart' and 'tieStop' fields which I will explain.

data Item = Note
             { pitch :: Pitch
             , end :: Loc
             , soundedEnd :: Maybe Loc
             , tieNext :: Bool
             , tiePrior :: Bool
             }

There is a concept of "tied notes". When two notes are tied
together, their durations are summed and they are sounded
continuously as if one note. Ties have several uses, but one
important one is to make a sound that begins in one measure and
ends in a later measure, by tying notes across measures.

The 'tieNext' field indicates if a note is tied to the following
note (that is, the next note of the same pitch). 'tiePrior'
indicates if tied to immediately prior note of same pitch.

A chain of notes can be tied. Notes in the middle with have
both tieNext and tiePrior set.

In the event a note is within a chain of ties, its 'soundedEnd'
field needs to be computed as Just e where e is the end of the
last note in the chain. This information is useful when rendering
the document as sound.

My problem is:

   - given a Doc in which all fields have been set EXCEPT soundedEnd
     (all soundedEnd's are given a default value of Nothing)
   - update those notes in the Doc which need to have soundedEnd set.
     This involves chasing down the chain of ties.

I can solve a simpler problem which is

-- Given a note with tieNext set, and a list of notes, find
-- the end Loc of the last note in the chain. Only notes
-- with the same pitch as 'firstNote' are considered when looking
-- for the chain of notes.
computeSoundedEnd :: Item -> [Item] -> Loc
computeSoundedEnd firstNote notes = compSndEnd (pitch firstNote) notes

compSndEnd :: Pitch -> [Item] -> Loc
compSndEnd _ [] = error "tie chain doesn't come to completion"
compSndEnd p (n:ns) = if pitch n == p
                         then if tieNext n
                           then if tiePrior n
                             then compSndEnd p ns
                             else error "illegal tie chain"
                           else if tiePrior n
                             then end n
                             else error "illegal tie chain"
                         else compSndEnd p ns

The thing that is hard for me to understand is how, in a functional
paradigm, to update the entire Doc by chasing down every tie and making
all necessary updates.

Thanks,
Mike