## Friday, September 13, 2013

### Ordered multisets

Partially ordered multisets are a generalization of sets, multisets, and lists so they provide a fairly general setting from which to describe mathematical collections. We can define series parallel collections that are closed under the fundamental operations of union and ordinal sum:
(= (ordinal-union {:x 1, :y 2} {:x 2, :y 1})
{:x 3, :y 3})
(= (ordinal-sum [1 2 3] [4 5 6])
[1 2 3 4 5 6])

The operation of union corresponds to the combination of multisets and the operation of the ordinal sum corresponds to the concatenation of lists. Things get really interesting once we combine these two operation together to get series parallel collections that cannot be classified as any of the familiar collection types.