-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/
-- | Composition trees for arbitrary monoids.
--
-- 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.
@package composition-tree
@version 0.2.0.4
-- | See Data.Compositions for normal day-to-day use. This module
-- contains the implementation of that module.
module Data.Compositions.Internal
-- | Returns true if the given tree is appropriately right-biased. Used for
-- the following internal debugging tests:
--
--
-- \(Compositions l) -> wellformed l
--
--
--
-- wellformed (mempty :: Compositions Element)
--
--
--
-- \(Compositions a) (Compositions b) -> wellformed (a <> b)
--
--
--
-- \(Compositions t) n -> wellformed (take n t)
--
--
--
-- \(Compositions t) n -> wellformed (drop n t)
--
wellformed :: (Monoid a, Eq a) => Compositions a -> Bool
-- | 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
--
newtype Compositions a
Tree :: [Node a] -> Compositions a
[unwrap] :: Compositions a -> [Node a]
data Node a
Node :: Int -> Maybe (Node a, Node a) -> !a -> Node a
[nodeSize] :: Node a -> Int
[nodeChildren] :: Node a -> Maybe (Node a, Node a)
[nodeValue] :: Node a -> !a
-- | Only valid if the function given is a monoid morphism
--
-- Otherwise, use fromList . map f . toList (which is much
-- slower).
unsafeMap :: (a -> b) -> Compositions a -> Compositions b
-- | 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)
--
drop :: Monoid a => Int -> Compositions a -> Compositions a
-- | 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
--
take :: Monoid a => Int -> Compositions a -> Compositions a
-- | Returns the composition of the first k elements of the
-- compositions list, doing only O(log k) compositions. Faster than
-- simply using take and then composed separately.
--
--
-- \(Compositions l) n -> takeComposed n l == composed (take n l)
--
--
--
-- \(Compositions l) -> takeComposed (length l) l == composed l
--
takeComposed :: Monoid a => Int -> Compositions a -> a
-- | A convenience alias for take and drop
--
--
-- \(Compositions l) i -> splitAt i l == (take i l, drop i l)
--
splitAt :: Monoid a => Int -> Compositions a -> (Compositions a, Compositions a)
-- | 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)
--
composed :: Monoid a => Compositions a -> a
-- | 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]
--
singleton :: Monoid a => a -> Compositions a
-- | 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)
--
length :: Compositions a -> Int
-- | 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
--
fromList :: Monoid a => [a] -> Compositions a
-- | 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
--
cons :: Monoid a => a -> Compositions a -> Compositions a
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.Compositions.Internal.Compositions a)
instance GHC.Base.Functor Data.Compositions.Internal.Node
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.Compositions.Internal.Node a)
instance GHC.Show.Show a => GHC.Show.Show (Data.Compositions.Internal.Node a)
instance GHC.Show.Show a => GHC.Show.Show (Data.Compositions.Internal.Compositions a)
instance (GHC.Base.Monoid a, GHC.Read.Read a) => GHC.Read.Read (Data.Compositions.Internal.Compositions a)
instance GHC.Base.Monoid a => GHC.Base.Monoid (Data.Compositions.Internal.Compositions a)
instance Data.Foldable.Foldable Data.Compositions.Internal.Compositions
-- | 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.
module Data.Compositions
-- | 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
--
data Compositions a
-- | 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]
--
singleton :: Monoid a => a -> Compositions a
-- | 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
--
cons :: Monoid a => a -> Compositions a -> Compositions a
-- | 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
--
fromList :: Monoid a => [a] -> Compositions a
-- | 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
--
take :: Monoid a => Int -> Compositions a -> Compositions a
-- | 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)
--
drop :: Monoid a => Int -> Compositions a -> Compositions a
-- | A convenience alias for take and drop
--
--
-- \(Compositions l) i -> splitAt i l == (take i l, drop i l)
--
splitAt :: Monoid a => Int -> Compositions a -> (Compositions a, Compositions a)
-- | 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)
--
composed :: Monoid a => Compositions a -> a
-- | Returns the composition of the first k elements of the
-- compositions list, doing only O(log k) compositions. Faster than
-- simply using take and then composed separately.
--
--
-- \(Compositions l) n -> takeComposed n l == composed (take n l)
--
--
--
-- \(Compositions l) -> takeComposed (length l) l == composed l
--
takeComposed :: Monoid a => Int -> Compositions a -> a
-- | 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)
--
length :: Compositions a -> Int
-- | Only valid if the function given is a monoid morphism
--
-- Otherwise, use fromList . map f . toList (which is much
-- slower).
unsafeMap :: (a -> b) -> Compositions a -> Compositions b
-- | See Data.Compositions.Snoc for normal day-to-day use. This
-- module contains the implementation of that module.
module Data.Compositions.Snoc.Internal
newtype Flip a
Flip :: a -> Flip a
[unflip] :: Flip a -> a
-- | 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
--
newtype Compositions a
C :: Compositions (Flip a) -> Compositions a
[unC] :: Compositions a -> Compositions (Flip a)
-- | 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
--
fromList :: Monoid a => [a] -> Compositions a
-- | 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]
--
singleton :: Monoid a => a -> Compositions a
-- | Only valid if the function given is a monoid morphism
--
-- Otherwise, use fromList . map f . toList (which is much
-- slower).
unsafeMap :: (a -> b) -> Compositions a -> Compositions b
-- | 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)
--
drop :: Monoid a => Int -> Compositions a -> Compositions a
-- | 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
--
take :: Monoid a => Int -> Compositions a -> Compositions a
-- | Returns the composition of the list with the first k elements
-- removed, doing only O(log k) compositions. Faster than simply using
-- drop and then composed separately.
--
--
-- \(Compositions l) n -> dropComposed n l == composed (drop n l)
--
--
--
-- \(Compositions l) -> dropComposed 0 l == composed l
--
dropComposed :: Monoid a => Int -> Compositions a -> a
-- | A convenience alias for take and drop
--
--
-- \(Compositions l) i -> splitAt i l == (take i l, drop i l)
--
splitAt :: Monoid a => Int -> Compositions a -> (Compositions a, Compositions a)
-- | 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)
--
composed :: Monoid a => Compositions a -> a
-- | 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)
--
length :: Compositions a -> Int
-- | 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]
--
snoc :: Monoid a => Compositions a -> a -> Compositions a
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.Compositions.Snoc.Internal.Compositions a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.Compositions.Snoc.Internal.Flip a)
instance GHC.Base.Functor Data.Compositions.Snoc.Internal.Flip
instance GHC.Base.Monoid a => GHC.Base.Monoid (Data.Compositions.Snoc.Internal.Compositions a)
instance Data.Foldable.Foldable Data.Compositions.Snoc.Internal.Compositions
instance GHC.Show.Show a => GHC.Show.Show (Data.Compositions.Snoc.Internal.Compositions a)
instance (GHC.Base.Monoid a, GHC.Read.Read a) => GHC.Read.Read (Data.Compositions.Snoc.Internal.Compositions a)
instance GHC.Base.Monoid a => GHC.Base.Monoid (Data.Compositions.Snoc.Internal.Flip a)
-- | 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.Snoc.Internal for gory implementation,
-- and Data.Compositions for the regular cons version.
module Data.Compositions.Snoc
-- | 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
--
data Compositions a
-- | 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]
--
singleton :: Monoid a => a -> Compositions a
-- | 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]
--
snoc :: Monoid a => Compositions a -> a -> Compositions a
-- | 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
--
fromList :: Monoid a => [a] -> Compositions a
-- | 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
--
take :: Monoid a => Int -> Compositions a -> Compositions a
-- | 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)
--
drop :: Monoid a => Int -> Compositions a -> Compositions a
-- | A convenience alias for take and drop
--
--
-- \(Compositions l) i -> splitAt i l == (take i l, drop i l)
--
splitAt :: Monoid a => Int -> Compositions a -> (Compositions a, Compositions a)
-- | 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)
--
composed :: Monoid a => Compositions a -> a
-- | Returns the composition of the list with the first k elements
-- removed, doing only O(log k) compositions. Faster than simply using
-- drop and then composed separately.
--
--
-- \(Compositions l) n -> dropComposed n l == composed (drop n l)
--
--
--
-- \(Compositions l) -> dropComposed 0 l == composed l
--
dropComposed :: Monoid a => Int -> Compositions a -> a
-- | 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)
--
length :: Compositions a -> Int
-- | Only valid if the function given is a monoid morphism
--
-- Otherwise, use fromList . map f . toList (which is much
-- slower).
unsafeMap :: (a -> b) -> Compositions a -> Compositions b