Safe Haskell | Trustworthy |
---|---|
Language | Haskell2010 |
A Compositions list module biased to snoccing, rather than to consing. Internally implemented the same way, just storing all elements in reverse.
See Data.Compositions.Internal for gory implementation, and Data.Compositions for the regular cons version.
- data Compositions a
- singleton :: Monoid a => a -> Compositions a
- snoc :: Monoid a => Compositions a -> 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
- dropComposed :: 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 left-associativity, in that we only support efficient snoccing
to the end of the list. This also means that the drop
operation can be inefficient. The append operation a <> b
performs O(b log (a + b)) element compositions, so you want the right-hand list b
to be as small as possible.
For a version biased to consing, see Data.Compositions. This gives the opposite performance characteristics,
where take
is slow and drop
is fast.
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 == snoc mempty x
\(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]
snoc :: Monoid a => Compositions a -> a -> Compositions a Source
Add a new element to the end of a compositions list. Performs O(log n) element compositions.
\(x :: Element) (Compositions xs) -> snoc xs x == xs <> singleton x
\(x :: Element) (Compositions xs) -> length (snoc xs x) == length xs + 1
Refinement of List snoc:
\(x :: Element) (xs :: [Element]) -> snoc (fromList xs) x == fromList (xs ++ [x])
\(x :: Element) (Compositions xs) -> toList (snoc xs x) == toList xs ++ [x]
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 O(log k) time.
\(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 the worst case, performs O(k log k) element compositions,
in order to maintain the left-associative bias. If you wish to run composed
on the result of drop
, use dropComposed
for better performance.
Rewrite RULES
are provided for compilers which support them.
\(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)
dropComposed :: 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).