[Haskell-beginners] music layout problem

[Michael Mossey]

I'm continuing to work on this music layout problem, and I'm trying
another angle.

A page of music is made of many individual symbols and graphical items
like lines and arcs. I decided to call a drawable symbol/item a
Grapheme. so


type MusicPage = [Grapheme]

The program also maintains the more fundamental description of music
in conceptual form---that is, notes, chords, time signatures, tempo
indications, etc. I decided to call bits of information about music
Datemes.

type MusicScore = [Dateme]

A function to lay out a musical page would have this signature:

layoutPage :: [Dateme] -> [Grapheme]

Now let's think about the structure of a page of music for a
moment. It's made of *systems*, which are groups of notes read from
left to right. A page consists of a number of systems stacked
vertically (like a page of text has lines of text stacked vertically).
The layout algorithm will fit as many systems as it can
into a page. When it runs out of space, it will stop (even if there
are Dateme left).

A layout algorithm in imperative pseudocode would look something like:

- initialize the list remainingDateme to the input list of Dateme
- loop
   - looking at the list of remainingDateme, make a system
   - try to fit the system to the page
   - if the system doesn't fit, break out of the loop
   - add the system to the page
   - drop the used Dateme from remainingDateme
   - if remainingDateme is empty, break out of the loop
   - go to top of loop

I tried to write this in Haskell, and it seem awkward. It would be
something like:

-- layout page, produce list of Grapheme and also list of
-- unused Dateme
layoutPage :: PageDimensions -> [Dateme] ->
               ( [Grapheme], [Dateme] )
layoutPage dim dateme = layoutPage' dim [] dateme

layoutPage' :: PageDimensions -> [Grapheme] -> [Dateme] ->
                ( [Grapheme], [Dateme] )
layoutPage' dim graphemeSoFar [] = ( graphemeSoFar, [] )
layoutPage' dim graphemeSoFar remainingDateme =
   let ( newGrapheme, remainingDateme', dim' ) = layoutSystem dim
                                                 remainingDateme
   in if null newGrapheme
      then ( graphemeSoFar, remainingDateme )
      else layoutPage' dim' (graphemeSoFar ++ newGrapheme) remainingDateme'

We assume this is defined elsewhere:

-- layoutSystem takes as input the current page dimensions (think of
-- the "current page dimensions" as the room *remaining* on the page),
-- and a list of Dateme, and returns the triple:
--   ( [Grapheme] for the new system, or null list if no additional system
--       can fit on the page,
--     remaining [Dateme] that are not consumed,
--     new page dimensions )
layoutSystem :: PageDimensions -> [Dateme] ->
                 ( [Grapheme], [Dateme], PageDimensions )