[Haskell-cafe] Syntax programming with lexemes rather than trees?

Stephen Tetley stephen.tetley at gmail.com
Wed Mar 24 05:44:03 EDT 2010

Hi Neil

Thanks - music has has lots of structure, true, but unfortunately the
structure is often arbitrary, sometimes even conflicting (with respect
to a nested representation).

I've tried various representations: plain algebraic data types, HOAS,
generics with KURE, tagless, attribute grammar with UUAG. From all
this, it turns out that the transformations I want to are pretty

- 'rename' pitch - two versions - one context free so I can use fmap;
the other context sensitive, so I use stmap - a variation of mapAccumL
coded as a typeclass - its surprising pleasant to use as an
alternative to a state monad when you can live with left-to-right
traversals only:

  class StateMap  f where
    stmap :: (st -> a -> (b, st)) -> st -> f a -> (f b, st)

- 'rename' duration - same thing, two different traversals one context
sensitive, one context free.

- metrical splitting - more complicated - segmenting note lists into
bars and beams groups (which must be communicated to LilyPond and ABC)
somewhat reminiscent of groupBy in Data.List but more involved. I've
rewritten the algorithm about 5 times, each time a slight improvement
though it still isn't pretty (not a big deal, however, so long as it

At the moment I can do quite a lot with what I've got, but its too
unwieldy for real use - recently adding support for above-staff fret
diagrams has caused a lot of duplicated code even though it should be
superficially simple (fret diagrams don't need tuplets or beam groups
in their note list syntax). So I need a more different representation.

Although Malcolm didn't mention it, his message reminded me of
streaming XML processing. I've found a few papers since by Alain
Frisch, Keisuke Nakano and colleagues that cast streaming in a
functional light, so I'll see how far I can get with a similar

Thanks again


More information about the Haskell-Cafe mailing list