-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | API for collection data structures.
--   
--   This package provides classes for a consistent API to data structures.
--   The behaviour of the interface is specified by QuickCheck properties.
--   It is intended as an evolution of the API of the data structures in
--   the <tt>containers</tt> package.
@package collections-api
@version 1.0.0.0


-- | Class of data structures that can be folded to a summary value.
module Data.Collections.Foldable

-- | Data structures that can be folded.
--   
--   Minimal complete definition: <a>foldMap</a> or <a>foldr</a>.
--   
--   For example, given a data type
--   
--   <pre>
--   data Tree a = Empty | Leaf a | Node (Tree a) a (Tree a)
--   </pre>
--   
--   a suitable instance would be
--   
--   <pre>
--   instance Foldable Tree
--      foldMap f Empty = mempty
--      foldMap f (Leaf x) = f x
--      foldMap f (Node l k r) = foldMap f l `mappend` f k `mappend` foldMap f r
--   </pre>
--   
--   This is suitable even for abstract types, as the monoid is assumed to
--   satisfy the monoid laws.
class Foldable t a | t -> a
fold :: (Foldable t a, Monoid a) => t -> a
foldMap :: (Foldable t a, Monoid m) => (a -> m) -> t -> m
foldr :: Foldable t a => (a -> b -> b) -> b -> t -> b
foldl :: Foldable t a => (b -> a -> b) -> b -> t -> b
foldr1 :: Foldable t a => (a -> a -> a) -> t -> a
foldl1 :: Foldable t a => (a -> a -> a) -> t -> a
null :: Foldable t a => t -> Bool
size :: Foldable t a => t -> Int
isSingleton :: Foldable t a => t -> Bool

-- | Fold over the elements of a structure, associating to the right, but
--   strictly.
foldr' :: Foldable t a => (a -> b -> b) -> b -> t -> b

-- | Fold over the elements of a structure, associating to the left, but
--   strictly.
foldl' :: Foldable t b => (a -> b -> a) -> a -> t -> a

-- | Monadic fold over the elements of a structure, associating to the
--   right, i.e. from right to left.
foldrM :: (Foldable t a, Monad m) => (a -> b -> m b) -> b -> t -> m b

-- | Monadic fold over the elements of a structure, associating to the
--   left, i.e. from left to right.
foldlM :: (Foldable t b, Monad m) => (a -> b -> m a) -> a -> t -> m a

-- | Map each element of a structure to an action, evaluate these actions
--   from left to right, and ignore the results.
traverse_ :: (Foldable t a, Applicative f) => (a -> f b) -> t -> f ()

-- | <a>for_</a> is <a>traverse_</a> with its arguments flipped.
for_ :: (Foldable t a, Applicative f) => t -> (a -> f b) -> f ()

-- | Evaluate each action in the structure from left to right, and ignore
--   the results.
sequenceA_ :: (Foldable t (f a), Applicative f) => t -> f ()

-- | The sum of a collection of actions, generalizing <tt>concat</tt>.
asum :: (Foldable t (f a), Alternative f) => t -> f a

-- | Map each element of a structure to a monadic action, evaluate these
--   actions from left to right, and ignore the results.
mapM_ :: (Foldable t a, Monad m) => (a -> m b) -> t -> m ()

-- | <a>forM_</a> is <a>mapM_</a> with its arguments flipped.
forM_ :: (Foldable t a, Monad m) => t -> (a -> m b) -> m ()

-- | Evaluate each monadic action in the structure from left to right, and
--   ignore the results.
sequence_ :: (Foldable t (m a), Monad m) => t -> m ()

-- | The sum of a collection of actions, generalizing <tt>concat</tt>.
msum :: (Foldable t (m a), MonadPlus m) => t -> m a

-- | List of elements of a structure.
toList :: Foldable t a => t -> [a]

-- | <a>and</a> returns the conjunction of a container of Bools. For the
--   result to be <a>True</a>, the container must be finite; <a>False</a>,
--   however, results from a <a>False</a> value finitely far from the left
--   end.
and :: Foldable t Bool => t -> Bool

-- | <a>or</a> returns the disjunction of a container of Bools. For the
--   result to be <a>False</a>, the container must be finite; <a>True</a>,
--   however, results from a <a>True</a> value finitely far from the left
--   end.
or :: Foldable t Bool => t -> Bool

-- | Determines whether any element of the structure satisfies the
--   predicate.
any :: Foldable t a => (a -> Bool) -> t -> Bool

-- | Determines whether all elements of the structure satisfy the
--   predicate.
all :: Foldable t a => (a -> Bool) -> t -> Bool

-- | The <a>sum</a> function computes the sum of the numbers of a
--   structure.
sum :: (Foldable t a, Num a) => t -> a

-- | The <a>product</a> function computes the product of the numbers of a
--   structure.
product :: (Foldable t a, Num a) => t -> a

-- | The largest element of the structure.
maximum :: (Foldable t a, Ord a) => t -> a

-- | The largest element of a non-empty structure with respect to the given
--   comparison function.
maximumBy :: Foldable t a => (a -> a -> Ordering) -> t -> a

-- | The least element of a non-null structure.
minimum :: (Foldable t a, Ord a) => t -> a

-- | The least element of a non-empty structure with respect to the given
--   comparison function.
minimumBy :: Foldable t a => (a -> a -> Ordering) -> t -> a

-- | Does the element occur in the structure?
elem :: (Foldable t a, Eq a) => a -> t -> Bool

-- | <a>notElem</a> is the negation of <a>elem</a>.
notElem :: (Foldable t a, Eq a) => a -> t -> Bool

-- | The <a>find</a> function takes a predicate and a structure and returns
--   the leftmost element of the structure matching the predicate, or
--   <a>Nothing</a> if there is no such element.
find :: Foldable t a => (a -> Bool) -> t -> Maybe a
instance Ix i => Foldable (Array i a) (i, a)
instance Foldable [a] a
instance Foldable (Maybe a) a


-- | This module defines a class framework for collection types. It
--   provides:
--   
--   <ul>
--   <li>Classes for the most common type of collections</li>
--   <li><i>View</i> types to change the type of a collection, so it
--   implements other classes. This allows to use types for purposes that
--   they are not originally designed for. (eg. <a>ElemsView</a>)</li>
--   <li>A few generic functions for handling collections.</li>
--   <li>Infix (operator) version of common functions.</li>
--   </ul>
--   
--   Should you need a more precise documentation,
--   <a>Data.Collections.Properties</a> lists laws that implementations are
--   entitled to assume.
--   
--   The classes defined in this module are intended to give hints about
--   performance. eg. if a function has a <tt><a>Map</a> c k v</tt>
--   context, this indicates that the function will perform better if
--   <tt>c</tt> has an efficitent lookup function.
--   
--   This class framework is based on ideas found in Simon Peyton Jones,
--   "<i>Bulk types with class</i>".
--   <a>http://research.microsoft.com/Users/simonpj/Papers/collections.ps.gz</a>
--   
--   Another inspiration source are the examples of MPTC and fuctional
--   dependencies in Oleg Kiselyov's many articles posted to the haskell
--   mailing list.
--   
--   This module name-clashes with a lot of Prelude functions, subsuming
--   those. The user is encouraged to import Prelude hiding the clashing
--   functions. Alternatively, it can be imported <tt>qualified</tt>.
module Data.Collections

-- | Class of collection with unobservable elements. It is the dual of the
--   <a>Foldable</a> class.
class Unfoldable c i | c -> i
insert :: Unfoldable c i => i -> c -> c
empty :: Unfoldable c i => c
singleton :: Unfoldable c i => i -> c
insertMany :: (Unfoldable c i, Foldable c' i) => c' -> c -> c
insertManySorted :: (Unfoldable c i, Foldable c' i) => c' -> c -> c

-- | Class of collection types.
class (Foldable c a, Unfoldable c a) => Collection c a | c -> a
filter :: Collection c a => (a -> Bool) -> c -> c
class Collection c o => SortingCollection c o
minView :: SortingCollection c o => c -> Maybe (o, c)

-- | Class of map-like types. (aka. for sparse associative types).
--   
--   In opposition of Indexed, Map supports unexisting value for some
--   indices.
class Monoid c => Map c k a | c -> k a
delete :: Map c k a => k -> c -> c
member :: Map c k a => k -> c -> Bool
union :: Map c k a => c -> c -> c
intersection :: Map c k a => c -> c -> c
difference :: Map c k a => c -> c -> c
isSubset :: Map c k a => c -> c -> Bool
isProperSubset :: Map c k a => c -> c -> Bool
lookup :: Map c k a => k -> c -> Maybe a
alter :: Map c k a => (Maybe a -> Maybe a) -> k -> c -> c
insertWith :: Map c k a => (a -> a -> a) -> k -> a -> c -> c
fromFoldableWith :: (Map c k a, Foldable l (k, a)) => (a -> a -> a) -> l -> c
foldGroups :: (Map c k a, Foldable l (k, b)) => (b -> a -> a) -> a -> l -> c
mapWithKey :: Map c k a => (k -> a -> a) -> c -> c
unionWith :: Map c k a => (a -> a -> a) -> c -> c -> c
intersectionWith :: Map c k a => (a -> a -> a) -> c -> c -> c
differenceWith :: Map c k a => (a -> a -> Maybe a) -> c -> c -> c
isSubmapBy :: Map c k a => (a -> a -> Bool) -> c -> c -> Bool
isProperSubmapBy :: Map c k a => (a -> a -> Bool) -> c -> c -> Bool

-- | The expression <tt>(<a>lookupWithDefault</a> def k map)</tt> returns
--   the value at key <tt>k</tt> or returns <tt>def</tt> when the key is
--   not in the map.
lookupWithDefault :: Map c k a => a -> k -> c -> a

-- | Union of many (key) sets, with combining function
unionsWith :: (Unfoldable s i, Map s k a, Foldable cs s) => (a -> a -> a) -> cs -> s

-- | Same as <a>intersectionWith</a>, but with a more general type.
intersectionWith' :: (Functor m, Map (m (O a b c)) k (O a b c)) => (a -> b -> c) -> m a -> m b -> m c

-- | Same as <a>differenceWith</a>, but with a more general type.
differenceWith' :: (Functor m, Map (m (O a b c)) k (O a b c)) => (a -> b -> Maybe c) -> m a -> m b -> m c
mapWithKey' :: (Functor m, Map (m (Either a b)) k (Either a b)) => (k -> a -> b) -> m a -> m b

-- | Infix version of <a>index</a>, with arguments swapped.
(!) :: Indexed c k v => c -> k -> v

-- | Class for set-like collection types. A set is really a map with no
--   value associated to the keys, so Set just states so.
class Map c k () => Set c k | c -> k
haddock_candy :: Set c k => c -> k

-- | Union of many (key) sets.
unions :: (Unfoldable s i, Map s k a, Foldable cs s) => cs -> s

-- | Tells whether a key is not a member of the keySet.
notMember :: Map c k a => k -> c -> Bool

-- | Infix version of <a>difference</a>. Difference of two (key) sets.
(\\) :: Map c k a => c -> c -> c

-- | Class of sequential-access types. In addition of the <a>Collection</a>
--   services, it provides deconstruction and concatenation.
class (Monoid c, Collection c a) => Sequence c a
take :: Sequence c a => Int -> c -> c
drop :: Sequence c a => Int -> c -> c
splitAt :: Sequence c a => Int -> c -> (c, c)
reverse :: Sequence c a => c -> c
front :: Sequence c a => c -> Maybe (a, c)
back :: Sequence c a => c -> Maybe (c, a)
cons :: Sequence c a => a -> c -> c
snoc :: Sequence c a => c -> a -> c
isPrefix :: (Sequence c a, Eq a) => c -> c -> Bool
head :: Sequence s a => s -> a
tail :: Sequence s a => s -> s

-- | Concatenate two sequences.
append :: Sequence c a => c -> c -> c

-- | The concatenation of all the elements of a container of sequences.
concat :: (Sequence s a, Foldable t s) => t -> s

-- | Map a function over all the elements of a container and concatenate
--   the resulting sequences.
concatMap :: (Sequence s b, Foldable t a) => (a -> s) -> t -> s

-- | Infix version of <a>cons</a>: add an element to the left end of a
--   sequence. Mnemonic: a triangle with the single element at the pointy
--   end.
(<|) :: Sequence c i => i -> c -> c

-- | Infix version of <a>snoc</a>: add an element to the right end of a
--   sequence. Mnemonic: a triangle with the single element at the pointy
--   end.
(|>) :: Sequence c i => c -> i -> c

-- | Infix verion of <a>append</a>. Concatenate two sequences.
(><) :: Sequence c a => c -> c -> c
class (Ix k, Foldable c (k, v), Indexed c k v) => Array c k v | c -> k v
bounds :: Array c k v => c -> (k, k)
array :: (Array c k v, Foldable l (k, v)) => (k, k) -> l -> c

-- | Class of indexed types. The collection is <tt>dense</tt>: there is no
--   way to <i>remove</i> an element nor for lookup to return <a>not
--   found</a>.
--   
--   In practice however, most shallow collection types will instanciate
--   this class in addition of <a>Map</a>, and leave the responsibility of
--   failure to the caller.
class Indexed c k v | c -> k v
index :: Indexed c k v => k -> c -> v
adjust :: Indexed c k v => (v -> v) -> k -> c -> c
inDomain :: Indexed c k v => k -> c -> Bool
(//) :: (Indexed c k v, Foldable l (k, v)) => c -> l -> c
accum :: (Indexed c k v, Foldable l (k, v')) => (v -> v' -> v) -> c -> l -> c

-- | Conversion from a Foldable to a Collection.
fromFoldable :: (Foldable f a, Collection c' a) => f -> c'

-- | Conversion from a Foldable to a Collection, with the <i>unchecked</i>
--   precondition that the input is sorted
fromAscFoldable :: (Foldable f a, Collection c' a) => f -> c'

-- | Converts a list into a collection.
fromList :: Collection c a => [a] -> c

-- | Specialized version of fromFoldableWith for lists.
fromListWith :: Map c k a => (a -> a -> a) -> [(k, a)] -> c

-- | Converts a list into a collection, with the precondition that the
--   input is sorted.
fromAscList :: Collection c a => [a] -> c

-- | <a>View</a> to the keys of a dictionnary
newtype KeysView m k v
KeysView :: m -> KeysView m k v
fromKeysView :: KeysView m k v -> m

-- | <a>View</a> to the elements of a dictionnary
newtype ElemsView m k v
ElemsView :: m -> ElemsView m k v
fromElemsView :: ElemsView m k v -> m
withKeys :: Collection m (k, v) => T (KeysView m k v) -> T m
withElems :: Collection m (k, v) => T (ElemsView m k v) -> T m
instance Map m k v => Map (KeysView m k v) k v
instance (Monoid m, Map m k v) => Monoid (KeysView m k v)
instance Unfoldable m (k, v) => Unfoldable (ElemsView m k v) (k, v)
instance Foldable m (k, v) => Foldable (ElemsView m k v) v
instance Unfoldable m (k, v) => Unfoldable (KeysView m k v) (k, v)
instance Foldable m (k, v) => Foldable (KeysView m k v) k


-- | The purpose of this module is twofold:
--   
--   <ol>
--   <li>Check instances of the classes in the collection framework.</li>
--   <li>Give those classes more formal semantics.</li>
--   </ol>
--   
--   Therefore, this acts as a contract between the collections users and
--   implementers.
--   
--   Each function in this module returns a list of <tt>(property_name,
--   propterty)</tt> for a given class (or set of classes). Each function
--   is parameterized on the type of the collection to check, so a value
--   witnessing the type must be passed. This value is guaranteed not to be
--   evaluated, so it can always be <a>undefined</a>.
--   
--   These properties allow to verify, with a high degree of confidence,
--   that instances of the classes defined in <tt>Data.Collections</tt>
--   satisfy the prescribed properties.
--   
--   You will note that properties depend on the <a>Eq</a> class. This
--   means that
--   
--   <ul>
--   <li>properties are verified up to <a>Eq</a> equivalence.</li>
--   <li>Infinite structures and other <tt>bottom</tt>s are not testable
--   with this module.</li>
--   </ul>
module Data.Collections.Properties

-- | unfoldable_properties returns the following properties:
--   
--   <ul>
--   <li><i><i>singleton</i></i></li>
--   </ul>
--   
--   <pre>
--   singleton a == insert a empty
--   </pre>
--   
--   <ul>
--   <li><i><i>insertMany</i></i></li>
--   </ul>
--   
--   <pre>
--   insertMany l c == Foldable.foldr insert c l
--   </pre>
--   
--   <ul>
--   <li><i><i>insertManySorted</i></i></li>
--   </ul>
--   
--   <pre>
--   insertManySorted l c == Foldable.foldr insert c l
--      where l = List.sort l0
--   </pre>
unfoldable_properties :: (Arbitrary c, Arbitrary a, Ord a, Show a, Show c, Eq c, Eq a, Unfoldable c a) => c -> [(Property, String)]

-- | foldable_properties returns the following properties:
--   
--   <ul>
--   <li><i><i>size</i></i></li>
--   </ul>
--   
--   <pre>
--   size c == foldr (const (+1)) 0 c
--   </pre>
--   
--   <ul>
--   <li><i><i>null</i></i></li>
--   </ul>
--   
--   <pre>
--   null c &lt;==&gt; all (const False) c
--   </pre>
--   
--   <ul>
--   <li><i><i>isSingleton</i></i></li>
--   </ul>
--   
--   <pre>
--   isSingleton c &lt;==&gt; size c == 1
--   </pre>
--   
--   <ul>
--   <li><i><i>eq_elem</i></i></li>
--   </ul>
--   
--   <pre>
--   c1 == c2 ==&gt; elem x c1 == elem x c2 -- note that the order of folding is not enforced, and that the converse is not true
--   </pre>
foldable_properties :: (Arbitrary c, Arbitrary a, Show a, Show c, Eq c, Eq a, Foldable c a) => c -> [(Property, String)]

-- | collection_properties returns the following properties:
--   
--   <ul>
--   <li><i><i>collection</i></i></li>
--   </ul>
--   
--   <pre>
--   foldr insert empty c == c
--   </pre>
--   
--   <ul>
--   <li><i><i>empty</i></i></li>
--   </ul>
--   
--   <pre>
--   null empty
--   </pre>
--   
--   <ul>
--   <li><i><i>insert1</i></i></li>
--   </ul>
--   
--   <pre>
--   a `elem` (insert a c)                                 -- insert puts the element in the collection
--   </pre>
--   
--   <ul>
--   <li><i><i>insert2</i></i></li>
--   </ul>
--   
--   <pre>
--   a /= a' ==&gt; (a' `elem` c &lt;==  a' `elem` (insert a c)) -- insert does not insert other elements
--   </pre>
--   
--   <ul>
--   <li><i><i>insert3</i></i></li>
--   </ul>
--   
--   <pre>
--   let c' = insert a c in x `elem` c &amp;&amp; y `elem` c ==&gt; x `elem` c' || y `elem` c' -- insert alters at most one element
--   </pre>
--   
--   <ul>
--   <li><i><i>filter</i></i></li>
--   </ul>
--   
--   <pre>
--   (a `elem` filter f c) &lt;==&gt; ((a `elem` c) &amp;&amp; f a)
--   </pre>
collection_properties :: (CoArbitrary i, Arbitrary c, Arbitrary i, Show i, Show c, Eq c, Eq i, Collection c i) => c -> [(Property, String)]

-- | map_properties returns the following properties:
--   
--   <ul>
--   <li><i><i>alter</i></i></li>
--   </ul>
--   
--   <pre>
--   lookup k (alter f k m) == f (lookup k m)
--   </pre>
--   
--   <ul>
--   <li><i><i>mapWithKey</i></i></li>
--   </ul>
--   
--   <pre>
--   lookup k (mapWithKey f m) == fmap (f k) (lookup k m)
--   </pre>
--   
--   <ul>
--   <li><i><i>unionWith</i></i></li>
--   </ul>
--   
--   <pre>
--   lookup k (unionWith f m1 m2) == case (lookup k m1, lookup k m2) of
--      (Nothing,Nothing) -&gt; Nothing
--      (Just x, Nothing) -&gt; Just x
--      (Nothing,Just x)  -&gt; Just x
--      (Just x, Just y)  -&gt; Just (f x y)
--   </pre>
--   
--   <ul>
--   <li><i><i>intersectionWith</i></i></li>
--   </ul>
--   
--   <pre>
--   lookup k (intersectionWith f m1 m2) == case (lookup k m1, lookup k m2) of
--      (Just x, Just y) -&gt; Just (f x y)
--      _ -&gt; Nothing
--   </pre>
--   
--   <ul>
--   <li><i><i>differenceWith</i></i></li>
--   </ul>
--   
--   <pre>
--   lookup k (differenceWith f m1 m2) == case (lookup k m1, lookup k m2) of
--      (Just x, Nothing) -&gt; Just x
--      (Just x, Just y)  -&gt; f x y
--      (Nothing, _)      -&gt; Nothing
--   </pre>
--   
--   <ul>
--   <li><i><i>isSubmapBy</i></i></li>
--   </ul>
--   
--   <pre>
--   isSubmapBy f m1 m2 &lt;==&gt; differenceWith (\x y-&gt;if f x y then Nothing else Just v) m1 m2 == mempty
--   </pre>
--   
--   <ul>
--   <li><i><i>isProperSubmapBy</i></i></li>
--   </ul>
--   
--   <pre>
--   isProperSubmapBy f m1 m2 &lt;==&gt; isSubmapBy f m1 m2 &amp;&amp; m1 /= m2
--   </pre>
--   
--   <ul>
--   <li><i><i>insertWith</i></i></li>
--   </ul>
--   
--   <pre>
--   insertWith f k a m == alter (\x -&gt; Just $ case x of {Nothing-&gt;a;Just a' -&gt; f a a'}) k m
--   </pre>
--   
--   <ul>
--   <li><i><i>fromFoldableWith</i></i></li>
--   </ul>
--   
--   <pre>
--   fromFoldableWith f l == foldr (uncurry (insertWith f)) mempty l
--   </pre>
--   
--   <ul>
--   <li><i><i>delete</i></i></li>
--   </ul>
--   
--   <pre>
--   delete k m == alter (const Nothing) k m
--   </pre>
--   
--   <ul>
--   <li><i><i>member</i></i></li>
--   </ul>
--   
--   <pre>
--   member k m &lt;==&gt; isJust (lookup k m)
--   </pre>
--   
--   <ul>
--   <li><i><i>union</i></i></li>
--   </ul>
--   
--   <pre>
--   union m1 m2 == unionWith const m1 m2
--   </pre>
--   
--   <ul>
--   <li><i><i>intersection</i></i></li>
--   </ul>
--   
--   <pre>
--   intersection m1 m2 == intersectionWith const m1 m2 
--   </pre>
--   
--   <ul>
--   <li><i><i>difference</i></i></li>
--   </ul>
--   
--   <pre>
--   difference m1 m2 == differenceWith (\_ _ -&gt; Nothing) m1 m2
--   </pre>
--   
--   <ul>
--   <li><i><i>subset</i></i></li>
--   </ul>
--   
--   <pre>
--   isSubset m1 m2 &lt;==&gt; isSubmapBy (\_ _ -&gt; True) m1 m2
--   </pre>
--   
--   <ul>
--   <li><i><i>properSubset</i></i></li>
--   </ul>
--   
--   <pre>
--   isProperSubset m1 m2 &lt;==&gt; isProperSubmapBy (\_ _ -&gt; True) m1 m2
--   </pre>
--   
--   <ul>
--   <li><i><i>mempty</i></i></li>
--   </ul>
--   
--   <pre>
--   lookup k mempty == Nothing
--   </pre>
--   
--   <ul>
--   <li><i><i>mappend</i></i></li>
--   </ul>
--   
--   <pre>
--   mappend m1 m2 == union m1 m2
--   </pre>
--   
--   <ul>
--   <li><i><i>eq_lookup</i></i></li>
--   </ul>
--   
--   <pre>
--   c1 == c2 ==&gt; lookup x c1 == lookup x c2 -- should really be: c1 == c2 &lt;==&gt; forall x. lookup x c1 == lookup x c2
--   </pre>
map_properties :: (CoArbitrary v, CoArbitrary k, Arbitrary m, Arbitrary k, Arbitrary v, Show k, Show v, Show m, Eq m, Eq v, Map m k v) => m -> [(Property, String)]

-- | map_unfold_properties returns the following properties:
--   
--   <ul>
--   <li><i><i>mempty</i></i></li>
--   </ul>
--   
--   <pre>
--   mempty == empty
--   </pre>
--   
--   <ul>
--   <li><i><i>insert</i></i></li>
--   </ul>
--   
--   <pre>
--   insert (k,v) m == insertWith (\x _ -&gt; x) k v m
--   </pre>
map_unfold_properties :: (Arbitrary m, Arbitrary k, Arbitrary v, Show k, Show v, Show m, Eq m, Eq v, Eq k, Map m k v, Collection m (k, v)) => m -> [(Property, String)]

-- | set_unfold_properties returns the following properties:
--   
--   <ul>
--   <li><i><i>mempty</i></i></li>
--   </ul>
--   
--   <pre>
--   mempty == empty
--   </pre>
--   
--   <ul>
--   <li><i><i>insert</i></i></li>
--   </ul>
--   
--   <pre>
--   insert k m == insertWith (\x _-&gt;x) k () m
--   </pre>
set_unfold_properties :: (Arbitrary m, Arbitrary k, Show k, Show m, Eq m, Eq k, Map m k (), Unfoldable m k) => m -> [(Property, String)]

-- | map_fold_properties returns the following properties:
--   
--   <ul>
--   <li><i><i>foldable</i></i></li>
--   </ul>
--   
--   <pre>
--   maybeToList (lookup k m) == map snd (List.filter ((== k) . fst) (toList m))
--   </pre>
--   
--   <ul>
--   <li><i><i>size</i></i></li>
--   </ul>
--   
--   <pre>
--   sizeExcept (alter f k m) == sizeExcept m
--     where sizeExcept m = size m - maybe 0 (const 1) (lookup k m)
--   </pre>
map_fold_properties :: (CoArbitrary v, Arbitrary m, Arbitrary k, Arbitrary v, Show k, Show v, Show m, Eq m, Eq v, Eq k, Map m k v, Collection m (k, v)) => m -> [(Property, String)]

-- | set_fold_properties returns the following properties:
--   
--   <ul>
--   <li><i><i>foldable</i></i></li>
--   </ul>
--   
--   <pre>
--   maybeToList (lookup k m) == map (const ()) (List.filter (== k) (toList m))
--   </pre>
--   
--   <ul>
--   <li><i><i>size</i></i></li>
--   </ul>
--   
--   <pre>
--   sizeExcept (alter f k m) == sizeExcept m
--     where sizeExcept m = size m - maybe 0 (const 1) (lookup k m)
--   </pre>
set_fold_properties :: (Arbitrary m, Arbitrary k, Show k, Show m, Eq m, Eq k, Map m k (), Foldable m k) => m -> [(Property, String)]

-- | indexed_map_properties returns the following properties:
--   
--   <ul>
--   <li><i><i>domain</i></i></li>
--   </ul>
--   
--   <pre>
--   k `inDomain` m &lt;==&gt; k `member` m
--   </pre>
--   
--   <ul>
--   <li><i><i>index</i></i></li>
--   </ul>
--   
--   <pre>
--   case lookup k m of {Just x -&gt; x == index k m; _ -&gt; True}
--   </pre>
indexed_map_properties :: (Arbitrary m, Arbitrary k, Arbitrary v, Show k, Show v, Show m, Eq m, Eq v, Map m k v, Indexed m k v) => m -> [(Property, String)]

-- | sequence_properties returns the following properties:
--   
--   <ul>
--   <li><i><i>fold0</i></i></li>
--   </ul>
--   
--   <pre>
--   foldMap f empty == mempty
--   </pre>
--   
--   <ul>
--   <li><i><i>fold1</i></i></li>
--   </ul>
--   
--   <pre>
--   foldMap f (x &lt;| s) == f x `mappend` foldMap f s
--   </pre>
--   
--   <ul>
--   <li><i><i>fold2</i></i></li>
--   </ul>
--   
--   <pre>
--   foldMap f (s |&gt; x) == foldMap f s `mappend` f x
--   </pre>
--   
--   <ul>
--   <li><i><i>fold3</i></i></li>
--   </ul>
--   
--   <pre>
--   foldMap f (s &gt;&lt; t) == foldMap f s `mappend` foldMap f t
--   </pre>
--   
--   <ul>
--   <li><i><i>front0</i></i></li>
--   </ul>
--   
--   <pre>
--   front empty == Nothing
--   </pre>
--   
--   <ul>
--   <li><i><i>front1</i></i></li>
--   </ul>
--   
--   <pre>
--   front (x &lt;| s) == Just (x,s)
--   </pre>
--   
--   <ul>
--   <li><i><i>front2</i></i></li>
--   </ul>
--   
--   <pre>
--   front (s |&gt; x) == case front s of {Nothing -&gt; Just (x, empty); Just (x',s') -&gt; Just (x', s' |&gt; x)}
--   </pre>
--   
--   <ul>
--   <li><i><i>front3</i></i></li>
--   </ul>
--   
--   <pre>
--   front (s &gt;&lt; t) == case front s of {Nothing -&gt; front t;         Just (x',s') -&gt; Just (x', s' &gt;&lt; t)}
--   </pre>
--   
--   <ul>
--   <li><i><i>back0</i></i></li>
--   </ul>
--   
--   <pre>
--   back empty == Nothing
--   </pre>
--   
--   <ul>
--   <li><i><i>back1</i></i></li>
--   </ul>
--   
--   <pre>
--   back (s |&gt; x) == Just (s,x)
--   </pre>
--   
--   <ul>
--   <li><i><i>back2</i></i></li>
--   </ul>
--   
--   <pre>
--   back (x &lt;| s) == case back s of {Nothing -&gt; Just (empty, x); Just (s',x') -&gt; Just (x &lt;| s', x')}
--   </pre>
--   
--   <ul>
--   <li><i><i>back3</i></i></li>
--   </ul>
--   
--   <pre>
--   back (t &gt;&lt; s) == case back s of {Nothing -&gt; back t;          Just (s',x') -&gt; Just (t &gt;&lt; s', x')}
--   </pre>
--   
--   <ul>
--   <li><i><i>drop1</i></i></li>
--   </ul>
--   
--   <pre>
--   drop 0     s == s
--   </pre>
--   
--   <ul>
--   <li><i><i>drop2</i></i></li>
--   </ul>
--   
--   <pre>
--   n&gt;0 ==&gt; drop (n+1) s == case front (drop n s) of Nothing -&gt; empty; Just (_,s') -&gt; s'
--   </pre>
--   
--   <ul>
--   <li><i><i>take1</i></i></li>
--   </ul>
--   
--   <pre>
--   take 0     s == empty
--   </pre>
--   
--   <ul>
--   <li><i><i>take2</i></i></li>
--   </ul>
--   
--   <pre>
--   n&gt;0 ==&gt; take (n+1) s == case front s of Nothing -&gt; empty; Just (x,s') -&gt; x &lt;| take n s'
--   </pre>
--   
--   <ul>
--   <li><i><i>reverse</i></i></li>
--   </ul>
--   
--   <pre>
--   foldMap f (reverse s) == getDual (foldMap (Dual . f) s)
--   </pre>
--   
--   <ul>
--   <li><i><i>mempty</i></i></li>
--   </ul>
--   
--   <pre>
--   mempty == empty
--   </pre>
--   
--   <ul>
--   <li><i><i>eq_fold</i></i></li>
--   </ul>
--   
--   <pre>
--   s1 == s2 ==&gt; foldMap f s1 == foldMap f s2
--   </pre>
sequence_properties :: (Arbitrary s, Arbitrary a, Show s, Show a, Eq s, Eq a, Sequence s a) => s -> [(Property, String)]

-- | indexed_properties returns the following properties:
--   
--   <ul>
--   <li><i><i>adjust</i></i></li>
--   </ul>
--   
--   <pre>
--   k `inDomain` m ==&gt; index k (adjust f k m) == f (index k m)
--   </pre>
indexed_properties :: (CoArbitrary v, Arbitrary m, Arbitrary k, Arbitrary v, Show k, Show v, Show m, Eq m, Eq v, Indexed m k v) => m -> [(Property, String)]

-- | indexed_sequence_properties returns the following properties:
--   
--   <ul>
--   <li><i><i>domain</i></i></li>
--   </ul>
--   
--   <pre>
--   k `inDomain` s &lt;==&gt; k &gt;= 0 &amp;&amp; k &lt; size s
--   </pre>
--   
--   <ul>
--   <li><i><i>left1</i></i></li>
--   </ul>
--   
--   <pre>
--   k `inDomain` s ==&gt; index (k+1)      (x &lt;| s) == index k s
--   </pre>
--   
--   <ul>
--   <li><i><i>left2</i></i></li>
--   </ul>
--   
--   <pre>
--   index 0          (x &lt;| s) == x
--   </pre>
--   
--   <ul>
--   <li><i><i>right1</i></i></li>
--   </ul>
--   
--   <pre>
--   k `inDomain` s ==&gt; index k          (s |&gt; x) == index k s
--   </pre>
--   
--   <ul>
--   <li><i><i>right2</i></i></li>
--   </ul>
--   
--   <pre>
--   index (size s)   (s |&gt; x) == x
--   </pre>
--   
--   <ul>
--   <li><i><i>append1</i></i></li>
--   </ul>
--   
--   <pre>
--   k `inDomain` t ==&gt; index (k+size s) (s &gt;&lt; t) == index k t
--   </pre>
--   
--   <ul>
--   <li><i><i>append2</i></i></li>
--   </ul>
--   
--   <pre>
--   k `inDomain` s ==&gt; index k          (s &gt;&lt; t) == index k s
--   </pre>
indexed_sequence_properties :: (Arbitrary s, Arbitrary a, Show s, Show a, Eq s, Eq a, Sequence s a, Indexed s Int a) => s -> [(Property, String)]
instance Show (a -> b)