úÎXÖW–      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. 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) %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;\(Compositions l) (Positive n) -> take n l <> drop n l == 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           compo_9TQ9jCFVg3K2WvV4JHVjfNData.Compositions.Internal Data.ListdroptakelengthData.CompositionsNodenodeSize nodeChildren nodeValue CompositionsTreeunwrap wellformed unsafeMap takeComposedsplitAtcomposed singletonfromListcons$fFoldableCompositions$fMonoidCompositionsbaseGHC.Basemconcat Data.FoldabletoListFoldable