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.