Composition trees for arbitrary monoids.
Switch branches/tags
Nothing to show
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Failed to load latest commit information.

Composition Trees

A compositions list or composition tree is a list data type where the elements are monoids, and the mconcat of any contiguous sublist can be computed in logarithmic time. A common use case of this type is in a wiki, version control system, or collaborative editor, where each change or delta would be stored in a list, and it is sometimes necessary to compute the composed delta between any two versions.

This package provides two versions of the data structure. One is strictly biased to right-associativity, in that we only support efficient consing to the front of the list, and the other is biased to left associativity, in that we only support efficient snoccing to the end of the list. The latter is implemented in terms of the former, just storing all elements in reverse.

This library is extensively covered by a comprehensive suite of QuickCheck properties, which are written into the documentation and run with doctest.

The actual package only depends on base, and is more or less straightforward Haskell code.

It is released under the BSD3 license.

Building, Installing

composition-tree is released on Hackage and is available in the usual way:

$ cabal update
$ cabal install composition-tree

You can also use stack if you prefer:

$ stack install composition-tree

A variety of stack-*.yaml files are provided for building against various LTS snapshots.


The full Haddock documentation is available on Hackage.

A composition tree can be constructed using fromList, or incrementally built up using mempty and cons. Use the provided take, drop, splitAt functions to get the sublist you want, and then use composed to extract the mconcat of that sublist.

For the regular cons-biased strutuure, takeComposed may be preferable if you just want the composed result of take. Similarly dropComposed for the snoc-biased version. A rewrite RULE is provided to do this automatically, but it may not fire as often as you’d like, so best be safe.

Future work

  • Perhaps it would be worth investigating relaxing the right/left-associative bias and thus drawing a middle ground allowing acceptable performance of both take and drop, by slightly reducing the performance of all the other operations.

Other notes

This library is designed to be used with my patches-vector library, which, along with this library gives you a basic version control system for vectors. Pretty neat!