Safe Haskell | Safe |
---|---|

Language | Haskell2010 |

Composition lists as an abstract type. See Data.Compositions.Internal for gory implementation details, and Data.Compositions.Snoc for an alternative implementation with different performance characteristics.

- data Compositions a
- singleton :: Monoid a => a -> Compositions a
- cons :: Monoid a => a -> Compositions a -> Compositions a
- fromList :: Monoid a => [a] -> Compositions a
- take :: Monoid a => Int -> Compositions a -> Compositions a
- drop :: Monoid a => Int -> Compositions a -> Compositions a
- splitAt :: Monoid a => Int -> Compositions a -> (Compositions a, Compositions a)
- composed :: Monoid a => Compositions a -> a
- takeComposed :: Monoid a => Int -> Compositions a -> a
- length :: Compositions a -> Int
- unsafeMap :: (a -> b) -> Compositions a -> Compositions b

# Definition

data Compositions a Source

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 version of a composition list is strictly biased to right-associativity, in that we only support efficient consing
to the front of the list. This also means that the `take`

operation can be inefficient. The append operation `a <> b`

performs O(a log (a + b)) element compositions, so you want
the left-hand list `a`

to be as small as possible.

For a version of the composition list with the opposite bias, and therefore opposite performance characteristics, see Data.Compositions.Snoc.

**Monoid laws:**

\(Compositions l) -> mempty <> l == l

\(Compositions l) -> l <> mempty == l

\(Compositions t) (Compositions u) (Compositions v) -> t <> (u <> v) == (t <> u) <> v

** toList is monoid morphism**:

toList (mempty :: Compositions Element) == []

\(Compositions a) (Compositions b) -> toList (a <> b) == toList a ++ toList b

Foldable Compositions Source | |

Eq a => Eq (Compositions a) Source | |

(Monoid a, Read a) => Read (Compositions a) Source | |

Show a => Show (Compositions a) Source | |

Monoid a => Monoid (Compositions a) Source |

# Construction

singleton :: Monoid a => a -> Compositions a Source

Construct a compositions list containing just one element.

\(x :: Element) -> singleton x == cons x mempty

\(x :: Element) -> composed (singleton x) == x

\(x :: Element) -> length (singleton x) == 1

**Refinement of singleton lists**:

\(x :: Element) -> toList (singleton x) == [x]

\(x :: Element) -> singleton x == fromList [x]

cons :: Monoid a => a -> Compositions a -> Compositions a Source

Add a new element to the front of a compositions list. Performs O(log n) element compositions.

\(x :: Element) (Compositions xs) -> cons x xs == singleton x <> xs

\(x :: Element) (Compositions xs) -> length (cons x xs) == length xs + 1

**Refinement of List (:)**:

\(x :: Element) (xs :: [Element]) -> cons x (fromList xs) == fromList (x : xs)

\(x :: Element) (Compositions xs) -> toList (cons x xs) == x : toList xs

fromList :: Monoid a => [a] -> Compositions a Source

Convert a compositions list into a list of elements. The other direction
is provided in the `Foldable`

instance. This will perform O(n log n) element compositions.

**Isomorphism to lists**:

\(Compositions x) -> fromList (toList x) == x

\(x :: [Element]) -> toList (fromList x) == x

**Is monoid morphism**:

fromList ([] :: [Element]) == mempty

\(a :: [Element]) b -> fromList (a ++ b) == fromList a <> fromList b

# Splitting

take :: Monoid a => Int -> Compositions a -> Compositions a Source

Return the compositions list containing only the first *k* elements
of the input. In the worst case, performs **O(k log k)** element compositions,
in order to maintain the right-associative bias. If you wish to run `composed`

on the result of `take`

, use `takeComposed`

for better performance.
Rewrite `RULES`

are provided for compilers which support them.

\(Compositions l) (Positive n) (Positive m) -> take n (take m l) == take m (take n l)

\(Compositions l) (Positive n) (Positive m) -> take m (take n l) == take (m `min` n) l

\(Compositions l) (Positive n) -> length (take n l) == min (length l) n

\(Compositions l) -> take (length l) l == l

\(Compositions l) (Positive n) -> take (length l + n) l == l

\(Positive n) -> take n (mempty :: Compositions Element) == mempty

**Refinement of take**:

\(l :: [Element]) n -> take n (fromList l) == fromList (List.take n l)

\(Compositions l) n -> toList (take n l) == List.take n (toList l)

\(Compositions l) (Positive n) -> take n l <> drop n l == l

drop :: Monoid a => Int -> Compositions a -> Compositions a Source

Return the compositions list with the first *k* elements removed, in O(log k) time.

\(Compositions l) (Positive n) (Positive m) -> drop n (drop m l) == drop m (drop n l)

\(Compositions l) (Positive n) (Positive m) -> drop n (drop m l) == drop (m + n) l

\(Compositions l) (Positive n) -> length (drop n l) == max (length l - n) 0

\(Compositions t) (Compositions u) -> drop (length t) (t <> u) == u

\(Compositions l) -> drop 0 l == l

\n -> drop n (mempty :: Compositions Element) == mempty

**Refinement of drop**:

\(l :: [Element]) n -> drop n (fromList l) == fromList (List.drop n l)

\(Compositions l) n -> toList (drop n l) == List.drop n (toList l)

splitAt :: Monoid a => Int -> Compositions a -> (Compositions a, Compositions a) Source

# Composition

composed :: Monoid a => Compositions a -> a Source

Compose every element in the compositions list. Performs only O(log n) compositions.

**Refinement of mconcat**:

\(l :: [Element]) -> composed (fromList l) == mconcat l

\(Compositions l) -> composed l == mconcat (toList l)

**Is a monoid morphism**:

\(Compositions a) (Compositions b) -> composed (a <> b) == composed a <> composed b

composed mempty == (mempty :: Element)

takeComposed :: Monoid a => Int -> Compositions a -> a Source

# Other

length :: Compositions a -> Int Source

Get the number of elements in the compositions list, in O(log n) time.

**Is a monoid morphism**:

length (mempty :: Compositions Element) == 0

\(Compositions a) (Compositions b) -> length (a <> b) == length a + length b

**Refinement of length**:

\(x :: [Element]) -> length (fromList x) == List.length x

\(Compositions x) -> length x == List.length (toList x)

unsafeMap :: (a -> b) -> Compositions a -> Compositions b Source

Only valid if the function given is a monoid morphism

Otherwise, use `fromList . map f . toList`

(which is much slower).