úΰè®},      !"#$%&'()*+ Trustworthy- A compositions list or composition tree> is a list data type where the elements are monoids, and the ,ÿ, 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  4 operation can be inefficient. The append operation a <> bR performs O(a log (a + b)) element compositions, so you want the left-hand list a to be as small as possible.wFor 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 == lU\(Compositions t) (Compositions u) (Compositions v) -> t <> (u <> v) == (t <> u) <> v- is monoid morphism:-toList (mempty :: Compositions Element) == []M\(Compositions a) (Compositions b) -> toList (a <> b) == toList a ++ toList boReturns true if the given tree is appropriately right-biased. Used for the following internal debugging tests:!\(Compositions l) -> wellformed l+wellformed (mempty :: Compositions Element)9\(Compositions a) (Compositions b) -> wellformed (a <> b),\(Compositions t) n -> wellformed (take n t),\(Compositions t) n -> wellformed (drop n t) 6Only valid if the function given is a monoid morphism Otherwise, use fromList . map f . toList (which is much slower). ,Return the compositions list with the first k$ elements removed, in O(log k) time.U\(Compositions l) (Positive n) (Positive m) -> drop n (drop m l) == drop m (drop n l)R\(Compositions l) (Positive n) (Positive m) -> drop n (drop m l) == drop (m + n) lK\(Compositions l) (Positive n) -> length (drop n l) == max (length l - n) 0C\(Compositions t) (Compositions u) -> drop (length t) (t <> u) == u"\(Compositions l) -> drop 0 l == l7\n -> drop n (mempty :: Compositions Element) == memptyRefinement of :F\(l :: [Element]) n -> drop n (fromList l) == fromList (List.drop n l)B\(Compositions l) n -> toList (drop n l) == List.drop n (toList l) 7Return the compositions list containing only the first k7 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  on the result of  , use  $ for better performance. Rewrite RULES/ are provided for compilers which support them.U\(Compositions l) (Positive n) (Positive m) -> take n (take m l) == take m (take n l)V\(Compositions l) (Positive n) (Positive m) -> take m (take n l) == take (m `min` n) lG\(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 == lB\(Positive n) -> take n (mempty :: Compositions Element) == memptyRefinement of :F\(l :: [Element]) n -> take n (fromList l) == fromList (List.take n l)B\(Compositions l) n -> toList (take n l) == List.take n (toList l);\(Compositions l) (Positive n) -> take n l <> drop n l == l %Returns the composition of the first k` elements of the compositions list, doing only O(log k) compositions. Faster than simply using   and then  separately.>\(Compositions l) n -> takeComposed n l == composed (take n l)<\(Compositions l) -> takeComposed (length l) l == composed l A convenience alias for   and  :\(Compositions l) i -> splitAt i l == (take i l, drop i l)UCompose every element in the compositions list. Performs only O(log n) compositions.Refinement of ,:7\(l :: [Element]) -> composed (fromList l) == mconcat l5\(Compositions l) -> composed l == mconcat (toList l)Is a monoid morphism:S\(Compositions a) (Compositions b) -> composed (a <> b) == composed a <> composed b&composed mempty == (mempty :: Element):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) == 1Refinement of singleton lists:.\(x :: Element) -> toList (singleton x) == [x].\(x :: Element) -> singleton x == fromList [x]FGet the number of elements in the compositions list, in O(log n) time.Is a monoid morphism:,length (mempty :: Compositions Element) == 0L\(Compositions a) (Compositions b) -> length (a <> b) == length a + length bRefinement of :9\(x :: [Element]) -> length (fromList x) == List.length x7\(Compositions x) -> length x == List.length (toList x)_Convert a compositions list into a list of elements. The other direction is provided in the .= instance. This will perform O(n log n) element compositions.Isomorphism to lists:-\(Compositions x) -> fromList (toList x) == x-\(x :: [Element]) -> toList (fromList x) == xIs monoid morphism:$fromList ([] :: [Element]) == memptyD\(a :: [Element]) b -> fromList (a ++ b) == fromList a <> fromList b^Add a new element to the front of a compositions list. Performs O(log n) element compositions.C\(x :: Element) (Compositions xs) -> cons x xs == singleton x <> xsH\(x :: Element) (Compositions xs) -> length (cons x xs) == length xs + 1Refinement of List (:):N\(x :: Element) (xs :: [Element]) -> cons x (fromList xs) == fromList (x : xs)H\(x :: Element) (Compositions xs) -> toList (cons x xs) == x : toList xs    Safe       Trustworthy-C A compositions list or composition tree> is a list data type where the elements are monoids, and the ,ÿ, 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  4 operation can be inefficient. The append operation a <> bR 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 ! is slow and   is fast. Monoid laws:%\(Compositions l) -> mempty <> l == l%\(Compositions l) -> l <> mempty == lU\(Compositions t) (Compositions u) (Compositions v) -> t <> (u <> v) == (t <> u) <> v- is monoid morphism:-toList (mempty :: Compositions Element) == []M\(Compositions a) (Compositions b) -> toList (a <> b) == toList a ++ toList b_Convert a compositions list into a list of elements. The other direction is provided in the .= instance. This will perform O(n log n) element compositions.Isomorphism to lists:-\(Compositions x) -> fromList (toList x) == x-\(x :: [Element]) -> toList (fromList x) == xIs monoid morphism:$fromList ([] :: [Element]) == memptyD\(a :: [Element]) b -> fromList (a ++ b) == fromList a <> fromList b: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) == 1Refinement of singleton lists:.\(x :: Element) -> toList (singleton x) == [x].\(x :: Element) -> singleton x == fromList [x]6Only valid if the function given is a monoid morphism Otherwise, use fromList . map f . toList (which is much slower). ,Return the compositions list with the first k2 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 $ on the result of  , use "$ for better performance. Rewrite RULES/ are provided for compilers which support them.U\(Compositions l) (Positive n) (Positive m) -> drop n (drop m l) == drop m (drop n l)R\(Compositions l) (Positive n) (Positive m) -> drop n (drop m l) == drop (m + n) lK\(Compositions l) (Positive n) -> length (drop n l) == max (length l - n) 0C\(Compositions t) (Compositions u) -> drop (length t) (t <> u) == u"\(Compositions l) -> drop 0 l == l7\n -> drop n (mempty :: Compositions Element) == memptyRefinement of :F\(l :: [Element]) n -> drop n (fromList l) == fromList (List.drop n l)B\(Compositions l) n -> toList (drop n l) == List.drop n (toList l)!7Return the compositions list containing only the first k, elements of the input, in O(log k) time.U\(Compositions l) (Positive n) (Positive m) -> take n (take m l) == take m (take n l)V\(Compositions l) (Positive n) (Positive m) -> take m (take n l) == take (m `min` n) lG\(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 == lB\(Positive n) -> take n (mempty :: Compositions Element) == memptyRefinement of :F\(l :: [Element]) n -> take n (fromList l) == fromList (List.take n l)B\(Compositions l) n -> toList (take n l) == List.take n (toList l);\(Compositions l) (Positive n) -> take n l <> drop n l == l"3Returns the composition of the list with the first kO elements removed, doing only O(log k) compositions. Faster than simply using   and then $ separately.>\(Compositions l) n -> dropComposed n l == composed (drop n l)3\(Compositions l) -> dropComposed 0 l == composed l#A convenience alias for ! and  :\(Compositions l) i -> splitAt i l == (take i l, drop i l)$UCompose every element in the compositions list. Performs only O(log n) compositions.Refinement of ,:7\(l :: [Element]) -> composed (fromList l) == mconcat l5\(Compositions l) -> composed l == mconcat (toList l)Is a monoid morphism:S\(Compositions a) (Compositions b) -> composed (a <> b) == composed a <> composed b&composed mempty == (mempty :: Element)%FGet the number of elements in the compositions list, in O(log n) time.Is a monoid morphism:,length (mempty :: Compositions Element) == 0L\(Compositions a) (Compositions b) -> length (a <> b) == length a + length bRefinement of :9\(x :: [Element]) -> length (fromList x) == List.length x7\(Compositions x) -> length x == List.length (toList x)&\Add a new element to the end of a compositions list. Performs O(log n) element compositions.C\(x :: Element) (Compositions xs) -> snoc xs x == xs <> singleton xH\(x :: Element) (Compositions xs) -> length (snoc xs x) == length xs + 1Refinement of List snoc:Q\(x :: Element) (xs :: [Element]) -> snoc (fromList xs) x == fromList (xs ++ [x])K\(x :: Element) (Compositions xs) -> toList (snoc xs x) == toList xs ++ [x] !"#$%&'()*+ !"#$%&+*)(' !"#$%& !"#$%&'()*+Safe  !"#$%& &! #$"%/        !"#$%#&'#&()compo_7ezT5Fe79Po26qUmHtHt3vData.Compositions.InternalData.Compositions.Snoc.Internal Data.ListdroptakelengthData.CompositionsData.Compositions.SnocNodenodeSize nodeChildren nodeValue CompositionsTreeunwrap wellformed unsafeMap takeComposedsplitAtcomposed singletonfromListcons$fFoldableCompositions$fMonoidCompositions$fReadCompositions$fShowCompositionsCunCFlipunflip dropComposedsnoc $fMonoidFlipbaseGHC.Basemconcat Data.FoldabletoListFoldable