Payasan notes - Concatenation vs. Extension

Classically constructive combinator libraries favour concatenation [1] - pretty printing is the obvious example: composition operators are functions Doc -> Doc -> Doc or their many-to-one, list equivalents [Doc] -> Doc. The Monoid typeclass is a fundamental part of Glasgow Haskell's standard libraries. When things don't fit Monoid, a standard exception is that they have more than one "plus" operation; pretty printing has two obvious versions of plus - vertical and horizontal concatenation.

However concatenation is not always the the most natural way to construct things. Sometimes extension feels more appropriate. Andy Gill's Graphiz/Dot and Oleg Kiselyov's SXML combinator libraries are compelling examples. In Dot, graphs are built in a monad which enables binding of fresh node ids and the subsequent use of these ids to construct edges. XML pages follow a tree structure - adding and extending leaves is natural whereas concatenating them is unusual and would demand a novel API.


[1] "Constructive" here means combinator libraries that construct something, e.g. a Doc in pretty printing or music (MIDI) in vintage Haskore. This is a loose term and can include, for example parser combinators. Whilst parser combinators process input, a user still builds a parser by concatenating smaller ones together.

payasan notes

Clocktime representation - a representation where timing (duration, onset) is represented by some real number and could support some notion of e.g. scaling.

The clock may commonly be seconds but it could be e.g. MIDI ticks.

Metrical representation - a representation where timing (duration) is represented by a symbolic value denoting a metric unit (e.g a quarter note) possibly dotted.

A metrical representation, like staff notation, can be thought of as tiled - no gaps (rests are concrete objects within the representation), no overlaps. Onset is implicit due to tiling. A metrical representation is expected to easily support concatenation.