[Haskell-beginners] Re: CORRECTED: making translation from imperative code]

Michael Mossey mpm at alumni.caltech.edu
Sat Apr 4 05:09:26 EDT 2009

Heinrich Apfelmus wrote:
> Michael Mossey wrote:
>> Read this version.
>> A composition consists of several voices or instruments, each indicated
>> by its own *staff*. Visually, a staff is a layout of items such as
>> notes, clef signs, and accidentals arranged horizontally from left to
>> right, representing increasing time.
>> A *system* is a set of staves stacked vertically that represent
>> instruments playing at the same time.
>> Here is a simple representation of a system, in which the pipe character
>> represents items. Note that some of the items are aligned vertically
>> meaning they will play at the same time. At other times, only one
>> staff contains a note.
>> staff 1:   |    |  | |
>> staff 2:     |  |    | |
>> Next we elaborate this model to show that items have visual width. Here
>> they are represented by clusters of x's with a pipe in the middle. The pipe
>> represents the part of the item that needs to be aligned with items on
>> other staves. For example, in the visual representation of a chord,
>> the part of the chord called the notehead needs to be aligned with
>> noteheads on other staves. (A chord includes other symbols, like
>> accidentals
>> and flags, which get drawn to the right or left of the notehead and don't
>> need to be aligned vertically with anything else.)
>> staff 1:  x|x xx|xx        x|x
>> staff 2:       x|x x|x xxxxx|xxxxx
>>            a    b   c       d
>> Here you can see that there is an additional constraint on layout,
>> which is that items need to have horizontal space around them so they
>> don't collide. For instance, the very wide item at 'd' (on staff 2) means
>> that the item on staff 1 at 'd' has to be positioned far to the right
>> of its previous item.

Hi Heinrich,

Okay, I read all of your email, and there is one problem. My layout problem is more 
complex than I communicated at first. Let me give a more detailed example:

staff 1:  xxxx|xxxx  x|x
staff 2:     x|xx xxxx|xx
staff 3:                  x|x
               a       b    c

There are two additional concerns to what you coded up. Notice that parts of events 
on different staves are allowed to overlap. To determine the spacing from a to b, one 
has to know the widths of items on each staff to see that they they can be placed 
with some overlap but won't collide. They can't be treated strictly as a compound 
item and "going blind" to the parts that make them up.

Secondly, look at the item on staff 3 at c. It has no prior item to avoid colliding 
with, and no items on other staves to line up with, but there is still a constraint 
on its position: c > b (by some amount that can be experimented with).

Here is something I coded up, but didn't test much (other than it compiles):

-- Item is a pair giving left width and right width.
-- Chunk represents items that must align. There may not be one on every staff,
-- hence the use of Maybe
type Item = (Int, Int)
type Chunk = [ Maybe Item ]

-- layout3, given a list of Chunks, will produce a list of integer positions where
-- they should be placed.
layout3 :: [ Chunk ] -> [ Int ]
layout3  cs        = layout3' cs (replicate (length cs) 0)
-- helper function layout3' takes list of chunks, integer list of "right extents"
-- (how far to the right each staff extends at that time), and minimum position
-- (which is, in this case, always 1 greater than prior placement position)
layout3' :: [ Chunk ] -> [ Int ] -> Int -> [ Int ]
layout3' [] _  _   = []
layout3' (c:cs) rs minP = p : layout3' cs rs' (p + 1) where
    p = maximum $ minP : (map place (zip c rs))
    rs' = map advance (zip c rs)
    place (item, r) = case item of
            Just ( left, right ) -> r + left
            _                    -> 0
    advance (item, p ) = case item of
            Just ( left, right ) -> p + right
            _                    -> p

The near identical functions place and advance really need to be merged.


More information about the Beginners mailing list