!"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~MPTC+FD experimental+jeanphilippe.bernardy (google mail address)%$Data structures that can be folded. Minimal complete definition:  or . For example, given a data type  9 data Tree a = Empty | Leaf a | Node (Tree a) a (Tree a) a suitable instance would be   instance Foldable Tree  foldMap f Empty = mempty  foldMap f (Leaf x) = f x M foldMap f (Node l k r) = foldMap f l `mappend` f k `mappend` foldMap f r CThis is suitable even for abstract types, as the monoid is assumed  to satisfy the monoid laws. 4Combine the elements of a structure using a monoid. /Map each element of the structure to a monoid,  and combine the results. 'Right-associative fold of a structure.  f z =  f z . &Left-associative fold of a structure.  f z =  f z .  A variant of  that has no base case, 7 and thus may only be applied to non-empty structures.  f =  f .  A variant of  that has no base case, 7 and thus may only be applied to non-empty structures.  f =  f . &Tells whether the structure is empty. #Returns the size of the structure. 7Tells whether the structure contains a single element. 'Fold over the elements of a structure, ) associating to the right, but strictly. /Monadic fold over the elements of a structure, 4 associating to the right, i.e. from right to left. 'Fold over the elements of a structure, ( associating to the left, but strictly. /Monadic fold over the elements of a structure, 3 associating to the left, i.e. from left to right. 7Map each element of a structure to an action, evaluate ; these actions from left to right, and ignore the results.  is  with its arguments flipped. >Map each element of a structure to a monadic action, evaluate ; these actions from left to right, and ignore the results.  is  with its arguments flipped. :Evaluate each action in the structure from left to right,  and ignore the results. BEvaluate each monadic action in the structure from left to right,  and ignore the results. 1The sum of a collection of actions, generalizing concat. 1The sum of a collection of actions, generalizing concat. !List of elements of a structure. DMap a function over all the elements of a container and concatenate  the resulting lists. ; returns the conjunction of a container of Bools. For the  result to be  , the container must be finite;  , however,  results from a ' value finitely far from the left end. ; returns the disjunction of a container of Bools. For the  result to be  , the container must be finite;  , however,  results from a ' value finitely far from the left end. IDetermines whether any element of the structure satisfies the predicate. HDetermines whether all elements of the structure satisfy the predicate. The : function computes the sum of the numbers of a structure. The > function computes the product of the numbers of a structure. &The largest element of the structure. AThe largest element of a non-empty structure with respect to the  given comparison function. +The least element of a non-null structure. ?The least element of a non-empty structure with respect to the  given comparison function. !)Does the element occur in the structure? "" is the negation of !. #The #8 function takes a predicate and a structure and returns B the leftmost element of the structure matching the predicate, or   if there is no such element. $  !"#$  !"#$    !"# experimental#jeanphilippe.bernardy; google mail.X$View" to the elements of a dictionnary %&'View to the keys of a dictionnary ()*<Class for set-like collection types. A set is really a map ' with no value associated to the keys,  so Set just states so. +.Dummy method for haddock to accept the class. ,>Class of map-like types. (aka. for sparse associative types). JIn opposition of Indexed, Map supports unexisting value for some indices. -NRemove a key from the keySet (and therefore the associated value in the Map). ..Tells whether an key is member of the keySet. /Union of two keySets. T When duplicates are encountered, the keys may come from any of the two input sets. 4 Values come from the map given as first arguement. 0Intersection of two keySets. SWhen duplicates are encountered, the keys may come from any of the two input sets. 4 Values come from the map given as first arguement. 1Difference of two keySets. ! Difference is to be read infix: a 1 b returns a set containing the  elements of a that are also absent from b. 2s1 2 s2C returns True iff. the keys in s1 form a subset of the keys in s2. 3s1 3 s2 returns True iff. s1 3 s2 and s1 /= s2 4!Lookup the value at a given key. 5,Change the value associated to a given key. ! represents no associated value. 6"Insert with a combining function. insertWith f key value m  will insert the pair  (key, value) into m if key does @ not exist in the map. If the key does exist, the function will  insert the pair (key, f new_value old_value). 7 Convert a  to a ,, with a combining function. 3 Note the applications of the combining function:  1fromFoldableWith (+) [(k,x1), (k,x2), ..., (k,xn)], = fromFoldable [(k, xn + (... + (x2 + x1)))]  or more generally fromFoldableWith f [(k,x) | x <- l]& = fromFoldable [(k,foldl1 (flip f) l)]  8) is probably less surprising, so use it. 8 Convert a  to a ,, with a combining function.  sfoldGroups f a l = let mkGroup g = (fst $ head g, foldr f a (map snd g)) in fromList . map mkGroup . groupBy ((==) on fst)) . toList 9-Apply a function over all values in the map. :"Union with a combining function. ;(Intersection with a combining function. <&Difference with a combining function. = isSubmapBy >isProperSubmapBy ?@if (l,r) = bounds c, then  inDomain k c  == l <= k <= r ACConstruct an array with the specified bounds and containing values ( for given indices within these bounds. AThe array is undefined (i.e. bottom) if any index in the list is E out of bounds. The Haskell 98 Report further specifies that if any E two associations in the list have the same index, the value at that 2 index is undefined (i.e. bottom). However in GHC's implementation, F the value at such an index is the value part of the last association  with that index in the list. 6Because the indices must be checked for these errors, A is E strict in the bounds argument and in the indices of the association C list, but nonstrict in the values. Thus, recurrences such as the  following are possible:  @ a = array (1,100) ((1,1) : [(i, i * a!(i-1)) | i <- [2..100]]) BNot every index within the bounds of the array need appear in the F association list, but the values associated with indices that do not ) appear will be undefined (i.e. bottom). GIf, in any dimension, the lower bound is greater than the upper bound, E then the array is legal, but empty. Indexing an empty array always " gives an array-bounds error, but @ still yields the bounds ' with which the array was constructed. BClass of indexed types.  The collection is dense: there is no way to remove an element nor for lookup  to return  not found. IIn practice however, most shallow collection types will instanciate this  class in addition of ,9, and leave the responsibility of failure to the caller. C index c k returns element associated to k D adjust f k c applies f to element associated to k' and returns the resulting collection. Eif  inDomain k c, then  index c k is guaranteed not to fail. FKConstructs a collection identical to the first argument except that it has 9 been updated by the associations in the right argument.  For example, if m is a 1-origin, n by n matrix, then   m//[((i,i), 0) | i <- [1..n]] 9is the same matrix, except with the diagonal zeroed. GG f8 takes an array and an association list and accumulates C pairs from the list into the array with the accumulating function f.  Thus  accumArray can be defined using G: H#Class of sequential-access types.  In addition of the Z9 services, it provides deconstruction and concatenation. I The first i elements of a sequence. J'Elements of a sequence after the first i. K#Split a sequence at a given index. LReverse a sequence. M$Analyse the left end of a sequence. N%Analyse the right end of a sequence. O2Add an element to the left end of a sequence. P/Add an element to the right end of a sequence. QThe Q3 function takes two seqences and returns True iff & the first is a prefix of the second. RSTFClass of collection with unobservable elements. It is the dual of the  class. U'natural', insertion of an element into a collection. VThe empty collection. W,Creates a collection with a single element. X'Insert all the elements of a foldable. YGSame as insertMany, but with the unchecked precondition that the input  is sorted. ZClass of collection types. [ filter f cE returns the collection of those elements that satisfy the predicate f. \,Conversion from a Foldable to a Collection. ]5Conversion from a Foldable to a Collection, with the  unchecked( precondition that the input is sorted ^#Converts a list into a collection. _SConverts a list into a collection, with the precondition that the input is sorted. `Concatenate two sequences. aInfix version of O0: add an element to the left end of a sequence. A Mnemonic: a triangle with the single element at the pointy end. bInfix version of P1: add an element to the right end of a sequence. B Mnemonic: a triangle with the single element at the pointy end. cInfix verion of `. Concatenate two sequences. dCThe concatenation of all the elements of a container of sequences. eDMap a function over all the elements of a container and concatenate  the resulting sequences. fghInfix version of C, with arguments swapped. i3Tells whether a key is not a member of the keySet. jThe expression (j def k map) returns  the value at key k or returns def! when the key is not in the map. k3Specialized version of fromFoldableWith for lists. lSame as ; , but with a more general type. mSame as < , but with a more general type. noInfix version of 1 . Difference of two (key) sets. Infix version of /. Union of two (key) sets. Infix version of 0". Intersection of two (key) sets. pUnion of many (key) sets. q2Union of many (key) sets, with combining function rst  !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrsPTUVWXYZ[RS,-./0123456789:;<=>jqlmnh*+pioHIJKLMNOPQfg`deabc?@ABCDEFG\]^k_'()$%&rsP$%&%&'()()*++,-./0123456789:;<=>-./0123456789:;<=>?@A@ABCDEFGCDEFGH IJKLMNOPQIJKLMNOPQRSSTUVWXYUVWXYZ[[\]^_`abcdefghijklmnopqrsMPTC, FD, undecidable instances experimental#jeanphilippe.bernardy; google mail.Logic equivalence t7foldable_properties returns the following properties:  size  # size c == foldr (const (+1)) 0 c  null  " null c <==> all (const False) c   isSingleton  ! isSingleton c <==> size c == 1  eq_elem { c1 == c2 ==> elem x c1 == elem x c2 -- note that the order of folding is not enforced, and that the converse is not true u9unfoldable_properties returns the following properties:   singleton   singleton a == insert a empty   insertMany  . insertMany l c == Foldable.foldr insert c l  insertManySorted 4 insertManySorted l c == Foldable.foldr insert c l  where l = List.sort l0 v9collection_properties returns the following properties:   collection   foldr insert empty c == c  empty   null empty  insert1  e a `elem` (insert a c) -- insert puts the element in the collection  insert2  a a /= a' ==> (a' `elem` c <== a' `elem` (insert a c)) -- insert does not insert other elements  insert3  v let c' = insert a c in x `elem` c && y `elem` c ==> x `elem` c' || y `elem` c' -- insert alters at most one element  filter 3 (a `elem` filter f c) <==> ((a `elem` c) && f a) w2map_properties returns the following properties:  alter  + lookup k (alter f k m) == f (lookup k m)   mapWithKey  7 lookup k (mapWithKey f m) == fmap (f k) (lookup k m)   unionWith  E lookup k (unionWith f m1 m2) == case (lookup k m1, lookup k m2) of " (Nothing,Nothing) -> Nothing ! (Just x, Nothing) -> Just x ! (Nothing,Just x) -> Just x ' (Just x, Just y) -> Just (f x y)  intersectionWith  L lookup k (intersectionWith f m1 m2) == case (lookup k m1, lookup k m2) of & (Just x, Just y) -> Just (f x y)  _ -> Nothing  differenceWith  J lookup k (differenceWith f m1 m2) == case (lookup k m1, lookup k m2) of ! (Just x, Nothing) -> Just x  (Just x, Just y) -> f x y " (Nothing, _) -> Nothing   isSubmapBy  c isSubmapBy f m1 m2 <==> differenceWith (\x y->if f x y then Nothing else Just v) m1 m2 == mempty  isProperSubmapBy  ? isProperSubmapBy f m1 m2 <==> isSubmapBy f m1 m2 && m1 /= m2   insertWith  Z insertWith f k a m == alter (\x -> Just $ case x of {Nothing->a;Just a' -> f a a'}) k m  fromFoldableWith  B fromFoldableWith f l == foldr (uncurry (insertWith f)) mempty l  delete  * delete k m == alter (const Nothing) k m  member  & member k m <==> isJust (lookup k m)  union  ' union m1 m2 == unionWith const m1 m2   intersection  6 intersection m1 m2 == intersectionWith const m1 m2   difference  = difference m1 m2 == differenceWith (\_ _ -> Nothing) m1 m2  subset  6 isSubset m1 m2 <==> isSubmapBy (\_ _ -> True) m1 m2   properSubset  B isProperSubset m1 m2 <==> isProperSubmapBy (\_ _ -> True) m1 m2  mempty   lookup k mempty == Nothing  mappend   mappend m1 m2 == union m1 m2   eq_lookup r c1 == c2 ==> lookup x c1 == lookup x c2 -- should really be: c1 == c2 <==> forall x. lookup x c1 == lookup x c2 x9map_unfold_properties returns the following properties:  mempty   mempty == empty  insert 1 insert (k,v) m == insertWith (\x _ -> x) k v m y7map_fold_properties returns the following properties:  foldable  N maybeToList (lookup k m) == map snd (List.filter ((== k) . fst) (toList m))  size + sizeExcept (alter f k m) == sizeExcept m A where sizeExcept m = size m - maybe 0 (const 1) (lookup k m) z9set_unfold_properties returns the following properties:  mempty   mempty == empty  insert , insert k m == insertWith (\x _->x) k () m {7set_fold_properties returns the following properties:  foldable  M maybeToList (lookup k m) == map (const ()) (List.filter (== k) (toList m))  size + sizeExcept (alter f k m) == sizeExcept m A where sizeExcept m = size m - maybe 0 (const 1) (lookup k m) |6indexed_properties returns the following properties:  adjust = k `inDomain` m ==> index k (adjust f k m) == f (index k m) }7sequence_properties returns the following properties:  fold0   foldMap f empty == mempty  fold1  2 foldMap f (x <| s) == f x `mappend` foldMap f s  fold2  2 foldMap f (s |> x) == foldMap f s `mappend` f x  fold3  : foldMap f (s >< t) == foldMap f s `mappend` foldMap f t  front0   front empty == Nothing  front1   front (x <| s) == Just (x,s)  front2  e front (s |> x) == case front s of {Nothing -> Just (x, empty); Just (x',s') -> Just (x', s' |> x)}  front3  e front (s >< t) == case front s of {Nothing -> front t; Just (x',s') -> Just (x', s' >< t)}  back0   back empty == Nothing  back1   back (s |> x) == Just (s,x)  back2  c back (x <| s) == case back s of {Nothing -> Just (empty, x); Just (s',x') -> Just (x <| s', x')}  back3  c back (t >< s) == case back s of {Nothing -> back t; Just (s',x') -> Just (t >< s', x')}  drop1   drop 0 s == s  drop2  W n>0 ==> drop (n+1) s == case front (drop n s) of Nothing -> empty; Just (_,s') -> s'  take1   take 0 s == empty  take2  Z n>0 ==> take (n+1) s == case front s of Nothing -> empty; Just (x,s') -> x <| take n s'  reverse  : foldMap f (reverse s) == getDual (foldMap (Dual . f) s)  mempty   mempty == empty  eq_fold , s1 == s2 ==> foldMap f s1 == foldMap f s2 ~?indexed_sequence_properties returns the following properties:  domain  + k `inDomain` s <==> k >= 0 && k < size s  left1  < k `inDomain` s ==> index (k+1) (x <| s) == index k s  left2  6 index 0 (x <| s) == x  right1  < k `inDomain` s ==> index k (s |> x) == index k s  right2  4 index (size s) (s |> x) == x  append1  < k `inDomain` t ==> index (k+size s) (s >< t) == index k t  append2 < k `inDomain` s ==> index k (s >< t) == index k s :indexed_map_properties returns the following properties:  domain  # k `inDomain` m <==> k `member` m  index ; case lookup k m of {Just x -> x == index k m; _ -> True} tuvwxyz{|}~ utvwxzy{}|~ tuvwxyz{|}~      !"#$%&'(()**+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~ gcollections-api-1.0.0.0Data.Collections.FoldableData.CollectionsData.Collections.PropertiesFoldablefoldfoldMapfoldrfoldlfoldr1foldl1nullsize isSingletonfoldr'foldrMfoldl'foldlM traverse_for_mapM_forM_ sequenceA_ sequence_asummsumtoListandoranyallsumproductmaximum maximumByminimum minimumByelemnotElemfind ElemsView fromElemsViewKeysView fromKeysViewSet haddock_candyMapdeletememberunion intersection differenceisSubsetisProperSubsetlookupalter insertWithfromFoldableWith foldGroups mapWithKey unionWithintersectionWithdifferenceWith isSubmapByisProperSubmapByArrayboundsarrayIndexedindexadjustinDomain//accumSequencetakedropsplitAtreversefrontbackconssnocisPrefixSortingCollectionminView Unfoldableinsertempty singleton insertManyinsertManySorted Collectionfilter fromFoldablefromAscFoldablefromList fromAscListappend<||>><concat concatMapheadtail! notMemberlookupWithDefault fromListWithintersectionWith'differenceWith' mapWithKey'\\unions unionsWithwithKeys withElemsfoldable_propertiesunfoldable_propertiescollection_propertiesmap_propertiesmap_unfold_propertiesmap_fold_propertiesset_unfold_propertiesset_fold_propertiesindexed_propertiessequence_propertiesindexed_sequence_propertiesindexed_map_propertiesbaseGHC.BaseGHC.List Data.Listghc-primGHC.BoolTrueFalse Data.MaybeNothingTORLunfold\//\<==>count