Portability  MPTC, FD, undecidable instances 

Stability  experimental 
Maintainer  jeanphilippe.bernardy; google mail. 
This module defines a class framework for collection types. It provides:
 Classes for the most common type of collections
 View 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.
ElemsView
)  A few generic functions for handling collections.
 Infix (operator) version of common functions.
Should you need a more precise documentation, Data.Collections.Properties 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
context, this indicates that the function
will perform better if Map
c k vc
has an efficitent lookup function.
This class framework is based on ideas found in Simon Peyton Jones, "Bulk types with class". http://research.microsoft.com/Users/simonpj/Papers/collections.ps.gz
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 nameclashes with a lot of Prelude functions, subsuming those.
The user is encouraged to import Prelude hiding the clashing functions.
Alternatively, it can be imported qualified
.
 class Unfoldable c i  c > i where
 insert :: i > c > c
 empty :: c
 singleton :: i > c
 insertMany :: Foldable c' i => c' > c > c
 insertManySorted :: Foldable c' i => c' > c > c
 class (Foldable c a, Unfoldable c a) => Collection c a  c > a where
 class Monoid c => Map c k a  c > k a where
 delete :: k > c > c
 member :: k > c > Bool
 union :: c > c > c
 intersection :: c > c > c
 difference :: c > c > c
 isSubset :: c > c > Bool
 lookup :: Monad m => k > c > m a
 alter :: (Maybe a > Maybe a) > k > c > c
 insertWith :: (a > a > a) > k > a > c > c
 fromFoldableWith :: Foldable l (k, a) => (a > a > a) > l > c
 foldGroups :: Foldable l (k, b) => (b > a > a) > a > l > c
 mapWithKey :: (k > a > a) > c > c
 unionWith :: (a > a > a) > c > c > c
 intersectionWith :: (a > a > a) > c > c > c
 differenceWith :: (a > a > Maybe a) > c > c > c
 isSubmapBy :: (a > a > Bool) > c > c > Bool
 lookupWithDefault :: Map c k a => a > k > c > a
 unionsWith :: (Unfoldable s i, Map s k a, Foldable cs s) => (a > a > a) > cs > s
 intersectionWith' :: (Functor m, Map (m (O a b c)) k (O a b c)) => (a > b > c) > m a > m b > m c
 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
 (!) :: Indexed c k v => c > k > v
 class Map c k () => Set c k  c > k where
 haddock_candy :: c > k
 unions :: (Unfoldable s i, Map s k a, Foldable cs s) => cs > s
 notMember :: Map c k a => k > c > Bool
 (\\) :: Map c k a => c > c > c
 class (Monoid c, Collection c a) => Sequence c a where
 head :: Sequence s a => s > a
 tail :: Sequence s a => s > s
 append :: Sequence c a => c > c > c
 concat :: (Sequence s a, Foldable t s) => t > s
 concatMap :: (Sequence s b, Foldable t a) => (a > s) > t > s
 (<) :: Sequence c i => i > c > c
 (>) :: Sequence c i => c > i > c
 (><) :: Sequence c a => c > c > c
 class (Ix k, Foldable c (k, v), Indexed c k v) => Array c k v  c > k v where
 class Indexed c k v  c > k v where
 fromFoldable :: (Foldable f a, Collection c' a) => f > c'
 fromAscFoldable :: (Foldable f a, Collection c' a) => f > c'
 fromList :: Collection c a => [a] > c
 fromListWith :: Map c k a => (a > a > a) > [(k, a)] > c
 fromAscList :: Collection c a => [a] > c
 newtype KeysView m k v = KeysView {
 fromKeysView :: m
 newtype ElemsView m k v = ElemsView {
 fromElemsView :: 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
 module Data.Collections.Foldable
 data Seq a
 data IntMap a
 data IntSet
 type StdSet = Set
 type StdMap = Map
 type AvlSet = Set
 type AvlMap = Map
 type RangedSet = RSet
Classes
Unfoldable
class Unfoldable c i  c > i whereSource
Class of collection with unobservable elements. It is the dual of the Foldable
class.
'natural' insertion of an element into a collection.
The empty collection.
Creates a collection with a single element.
insertMany :: Foldable c' i => c' > c > cSource
Insert all the elements of a foldable.
insertManySorted :: Foldable c' i => c' > c > cSource
Same as insertMany, but with the unchecked precondition that the input Foldable
is sorted.
Unfoldable ByteString Word8  
Unfoldable ByteString Word8  
Unfoldable IntSet Int  
Unfoldable [a] a  
Ord a => Unfoldable (Set a) a  
Unfoldable (Seq a) a  
Enum a => Unfoldable (Set a) a  
Ord a => Unfoldable (Set a) a  
DiscreteOrdered a => Unfoldable (RangedSet a) a  
Eq a => Unfoldable (SetList [a]) a  
Unfoldable (IntMap a) (Int, a)  
Ord k => Unfoldable (Map k a) (k, a)  
Ord k => Unfoldable (Map k a) (k, a)  
Unfoldable m (k, v) => Unfoldable (ElemsView m k v) (k, v)  
Unfoldable m (k, v) => Unfoldable (KeysView m k v) (k, v)  
(Ord k, Sequence c (k, v)) => Unfoldable (AssocList c k v) (k, v)  
(Ord k, Sequence s k) => Unfoldable (Trie s k v) (s, v) 
Collection
class (Foldable c a, Unfoldable c a) => Collection c a  c > a whereSource
Class of collection types.
filter :: (a > Bool) > c > cSource
filter f c
returns the collection of those elements that satisfy the predicate f
.
Collection ByteString Word8  
Collection ByteString Word8  
Collection IntSet Int  
Collection [a] a  
Ord a => Collection (Set a) a  
Collection (Seq a) a  
Enum a => Collection (Set a) a  
Ord a => Collection (Set a) a  
Eq a => Collection (SetList [a]) a  
Collection (IntMap a) (Int, a)  
Ord k => Collection (Map k a) (k, a)  
Ord k => Collection (Map k a) (k, a)  
(Ord k, Sequence c (k, v)) => Collection (AssocList c k v) (k, v)  
(Ord k, Sequence s k) => Collection (Trie s k v) (s, v) 
Map
class Monoid c => Map c k a  c > k a whereSource
Class of maplike types. (aka. for sparse associative types).
In opposition of Indexed, Map supports unexisting value for some indices.
Remove a key from the keySet (and therefore the associated value in the Map).
member :: k > c > BoolSource
Tells whether an key is member of the keySet.
Union of two keySets. When duplicates are encountered, the keys may come from any of the two input sets. Values come from the map given as first arguement.
intersection :: c > c > cSource
Intersection of two keySets.
When duplicates are encountered, the keys may come from any of the two input sets. Values come from the map given as first arguement.
difference :: c > c > cSource
Difference of two keySets.
Difference is to be read infix: a
returns a set containing the
elements of difference
ba
that are also absent from b
.
isSubset :: c > c > BoolSource
s1
returns True iff. the keys in s1 form a subset of the keys in s2.
isSubset
s2
lookup :: Monad m => k > c > m aSource
Lookup the value at a given key.
alter :: (Maybe a > Maybe a) > k > c > cSource
Change the value associated to a given key. Nothing
represents no associated value.
insertWith :: (a > a > a) > k > a > c > cSource
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)
.
fromFoldableWith :: Foldable l (k, a) => (a > a > a) > l > cSource
Convert a Foldable
to a Map
, with a combining function.
Note the applications of the combining function:
fromFoldableWith (+) [(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)]
foldGroups
is probably less surprising, so use it.
foldGroups :: Foldable l (k, b) => (b > a > a) > a > l > cSource
Convert a Foldable
to a Map
, with a combining function.
foldGroups f a l = let mkGroup g = (fst $ head g, foldr f a (map snd g)) in fromList . map mkGroup . groupBy ((==)
on
fst)) . toList
mapWithKey :: (k > a > a) > c > cSource
Apply a function over all values in the map.
unionWith :: (a > a > a) > c > c > cSource
Union with a combining function.
intersectionWith :: (a > a > a) > c > c > cSource
Intersection with a combining function.
differenceWith :: (a > a > Maybe a) > c > c > cSource
Difference with a combining function.
isSubmapBy :: (a > a > Bool) > c > c > BoolSource
isSubmapBy
Map IntSet Int ()  
Map (IntMap a) Int a  
Ord a => Map (Set a) a ()  
Enum a => Map (Set a) a ()  
Ord a => Map (Set a) a ()  
DiscreteOrdered a => Map (RangedSet a) a ()  
Eq a => Map (SetList [a]) a ()  
Ord k => Map (Map k a) k a  
Ord k => Map (Map k a) k a  
Map m k v => Map (KeysView m k v) k v  
(Ord k, Sequence c (k, v), Monoid (AssocList c k v)) => Map (AssocList c k v) k v  
(Ord k, Sequence s k) => Map (Trie s k v) s v 
lookupWithDefault :: Map c k a => a > k > c > aSource
The expression (
returns
the value at key lookupWithDefault
def k map)k
or returns def
when the key is not in the map.
unionsWith :: (Unfoldable s i, Map s k a, Foldable cs s) => (a > a > a) > cs > sSource
Union of many (key) sets, with combining function
intersectionWith' :: (Functor m, Map (m (O a b c)) k (O a b c)) => (a > b > c) > m a > m b > m cSource
Same as intersectionWith
, 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 cSource
Same as differenceWith
, but with a more general type.
mapWithKey' :: (Functor m, Map (m (Either a b)) k (Either a b)) => (k > a > b) > m a > m bSource
Set
class Map c k () => Set c k  c > k whereSource
Class for setlike collection types. A set is really a map with no value associated to the keys, so Set just states so.
haddock_candy :: c > kSource
Dummy method for haddock to accept the class.
unions :: (Unfoldable s i, Map s k a, Foldable cs s) => cs > sSource
Union of many (key) sets.
(\\) :: Map c k a => c > c > cSource
Infix version of difference
. Difference of two (key) sets.
Sequence
class (Monoid c, Collection c a) => Sequence c a whereSource
Class of sequentialaccess types.
In addition of the Collection
services, it provides deconstruction and concatenation.
The first i
elements of a sequence.
Elements of a sequence after the first i
.
splitAt :: Int > c > (c, c)Source
Split a sequence at a given index.
Reverse a sequence.
front :: Monad m => c > m (a, c)Source
Analyse the left end of a sequence.
back :: Monad m => c > m (c, a)Source
Analyse the right end of a sequence.
Add an element to the left end of a sequence.
Add an element to the right end of a sequence.
isPrefix :: Eq a => c > c > BoolSource
The isPrefix
function takes two seqences and returns True iff
the first is a prefix of the second.
Sequence ByteString Word8  
Sequence ByteString Word8  
Sequence [a] a  
Sequence (Seq a) a 
concat :: (Sequence s a, Foldable t s) => t > sSource
The concatenation of all the elements of a container of sequences.
concatMap :: (Sequence s b, Foldable t a) => (a > s) > t > sSource
Map a function over all the elements of a container and concatenate the resulting sequences.
(<) :: Sequence c i => i > c > cSource
Infix version of cons
: add an element to the left end of a sequence.
Mnemonic: a triangle with the single element at the pointy end.
(>) :: Sequence c i => c > i > cSource
Infix version of snoc
: add an element to the right end of a sequence.
Mnemonic: a triangle with the single element at the pointy end.
Others
class (Ix k, Foldable c (k, v), Indexed c k v) => Array c k v  c > k v whereSource
if (l,r) = bounds c
, then inDomain k c == l <= k <= r
array :: Foldable l (k, v) => (k, k) > l > cSource
Construct an array with the specified bounds and containing values for given indices within these bounds.
The array is undefined (i.e. bottom) if any index in the list is out of bounds. The Haskell 98 Report further specifies that if any two associations in the list have the same index, the value at that index is undefined (i.e. bottom). However in GHC's implementation, the value at such an index is the value part of the last association with that index in the list.
Because the indices must be checked for these errors, array
is
strict in the bounds argument and in the indices of the association
list, but nonstrict in the values. Thus, recurrences such as the
following are possible:
a = array (1,100) ((1,1) : [(i, i * a!(i1))  i < [2..100]])
Not every index within the bounds of the array need appear in the association list, but the values associated with indices that do not appear will be undefined (i.e. bottom).
If, in any dimension, the lower bound is greater than the upper bound,
then the array is legal, but empty. Indexing an empty array always
gives an arraybounds error, but bounds
still yields the bounds
with which the array was constructed.
class Indexed c k v  c > k v whereSource
Class of indexed types.
The collection is dense
: there is no way to remove an element nor for lookup
to return not found.
In practice however, most shallow collection types will instanciate this
class in addition of Map
, and leave the responsibility of failure to the caller.
index c k
returns element associated to k
adjust :: (v > v) > k > c > cSource
adjust f k c
applies f
to element associated to k
and returns the resulting collection.
inDomain :: k > c > BoolSource
if inDomain k c
, then index c k
is guaranteed not to fail.
(//) :: Foldable l (k, v) => c > l > cSource
Constructs a collection identical to the first argument except that it has
been updated by the associations in the right argument.
For example, if m
is a 1origin, n
by n
matrix, then
m//[((i,i), 0)  i < [1..n]]
is the same matrix, except with the diagonal zeroed.
accum :: Foldable l (k, v') => (v > v' > v) > c > l > cSource
Indexed ByteString Int Word8  
Indexed ByteString Int Word8  
Indexed [a] Int a  
Indexed (IntMap a) Int a  
Indexed (Seq a) Int a  
Ix i => Indexed (Array i e) i e  
Ord k => Indexed (Map k a) k a  
Ord k => Indexed (Map k a) k a  
(Ord k, Sequence c (k, v)) => Indexed (AssocList c k v) k v  
(Ord k, Foldable s k) => Indexed (Trie s k v) s v 
Conversions
fromFoldable :: (Foldable f a, Collection c' a) => f > c'Source
Conversion from a Foldable to a Collection.
fromAscFoldable :: (Foldable f a, Collection c' a) => f > c'Source
Conversion from a Foldable to a Collection, with the unchecked precondition that the input is sorted
fromList :: Collection c a => [a] > cSource
Converts a list into a collection.
fromListWith :: Map c k a => (a > a > a) > [(k, a)] > cSource
Specialized version of fromFoldableWith for lists.
fromAscList :: Collection c a => [a] > cSource
Converts a list into a collection, with the precondition that the input is sorted.
Views
View to the keys of a dictionnary
KeysView  

newtype ElemsView m k v Source
View to the elements of a dictionnary
ElemsView  

Foldable m (k, v) => Foldable (ElemsView m k v) v  
Unfoldable m (k, v) => Unfoldable (ElemsView m k v) (k, v) 
withKeys :: Collection m (k, v) => T (KeysView m k v) > T mSource
withElems :: Collection m (k, v) => T (ElemsView m k v) > T mSource
Foldable
module Data.Collections.Foldable
Concrete collection types
data Seq a
Generalpurpose finite sequences.
Monad Seq  
Functor Seq  
Typeable1 Seq  
MonadPlus Seq  
Foldable Seq  
Traversable Seq  
Eq a => Eq (Seq a)  
Data a => Data (Seq a)  
Ord a => Ord (Seq a)  
Read a => Read (Seq a)  
Show a => Show (Seq a)  
Monoid (Seq a)  
Foldable (Seq a) a  
Sequence (Seq a) a  
Unfoldable (Seq a) a  
Collection (Seq a) a  
Indexed (Seq a) Int a 
data IntMap a
A map of integers to values a
.
Functor IntMap  
Typeable1 IntMap  
Foldable IntMap  
Traversable IntMap  
Eq a => Eq (IntMap a)  
Data a => Data (IntMap a)  
Ord a => Ord (IntMap a)  
Read e => Read (IntMap e)  
Show a => Show (IntMap a)  
Monoid (IntMap a)  
Map (IntMap a) Int a  
Indexed (IntMap a) Int a  
Foldable (IntMap a) (Int, a)  
Unfoldable (IntMap a) (Int, a)  
Collection (IntMap a) (Int, a) 
data IntSet
A set of integers.