Safe Haskell  Trustworthy 

Language  Haskell2010 
See Data.Compositions.Snoc for normal daytoday use. This module contains the implementation of that module.
 newtype Flip a = Flip {
 unflip :: a
 newtype Compositions a = C {
 unC :: Compositions (Flip a)
 fromList :: Monoid a => [a] > Compositions a
 singleton :: Monoid a => a > Compositions a
 unsafeMap :: (a > b) > Compositions a > Compositions b
 drop :: Monoid a => Int > Compositions a > Compositions a
 take :: Monoid a => Int > Compositions a > Compositions a
 dropComposed :: Monoid a => Int > Compositions a > a
 splitAt :: Monoid a => Int > Compositions a > (Compositions a, Compositions a)
 composed :: Monoid a => Compositions a > a
 length :: Compositions a > Int
 snoc :: Monoid a => Compositions a > a > Compositions a
Documentation
>>>
:set XScopedTypeVariables
>>>
import Control.Applicative
>>>
import Test.QuickCheck
>>>
import qualified Data.List as List
>>>
type Element = [Int]
>>>
newtype C = Compositions (Compositions Element) deriving (Show, Eq)
>>>
instance (Monoid a, Arbitrary a) => Arbitrary (Compositions a) where arbitrary = fromList <$> arbitrary
>>>
instance Arbitrary C where arbitrary = Compositions <$> arbitrary
newtype 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 leftassociativity, 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 righthand 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
C  

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 #  
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
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]
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).
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 leftassociative 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)
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
dropComposed :: Monoid a => Int > Compositions a > a Source #
splitAt :: Monoid a => Int > Compositions a > (Compositions a, Compositions a) Source #
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)
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)
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]