 Haskell Hierarchical Libraries (collections package)  Contents  Index 

Data.Collections  Portability  MPTC, FD, undecidable instances  Stability  experimental  Maintainer  jeanphilippe.bernardy; google mail. 





Description 
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 Map c k v context, this indicates that the function
will perform better if c 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.


Synopsis 

class Foldable c o => Collection c i o  c > i o where    class Collection c a a => Collection' c a   unfold :: Collection c a a => (b > Maybe (a, b)) > b > c   class Monoid c => Map c k a  c > k a where    lookupWithDefault :: Map c k a => a > k > c > a   unionsWith :: (Collection s i o, 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    unions :: (Collection s i o, 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 a) => Sequence c a where    head :: Sequence s a => s > a   tail :: Sequence s a => s > s   find :: Foldable t a => (a > Bool) > t > Maybe a   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 a) => f > c'   fromAscFoldable :: (Foldable f a, Collection c' a a) => f > c'   fromList :: Collection c a a => [a] > c   fromListWith :: Map c k a => (a > a > a) > [(k, a)] > c   fromAscList :: Collection c a a => [a] > c   newtype KeysView m k v = KeysView {}   newtype ElemsView m k v = ElemsView {}   withKeys :: Collection m (k, v) (k, v) => T (KeysView m k v) > T m   withElems :: Collection m (k, v) (k, v) => T (ElemsView m k v) > T m   module Data.Collections.Foldable   Seq   IntMap   IntSet   type StdSet = Set   type StdMap = Map   type AvlSet = Set   type AvlMap = Map 



Classes


Collection


class Foldable c o => Collection c i o  c > i o where 
Class of collection types.
 i values are inserted into the collection.
 o values are extracted out of the collection.
Having two extra parameters allows for:
 unobservable collections when o = ()
 "readonly" collections when i = Void
 Views over only some projection of the element (see KeysView and ElemsView)
Also, please note that:
 neither map nor fmap is in here, use Functor or the alternate Functor for that purpose.
 extract :: c > Maybe (o,c) to take a random element is not there either.
  Methods  empty :: c  The empty collection.
  isSingleton :: c > Bool  Tells whether the collection contains a single element.
  filter :: (o > Bool) > c > c  filter f c returns the collection of those elements that satisfy the predicate f.
  insert :: i > c > c  'natural' insertion of an element into a collection.
  singleton :: i > c  Creates a collection with a single element.
  insertMany :: Foldable c' i => c' > c > c  Insert all the elements of a foldable.
  insertManySorted :: Foldable c' i => c' > c > c  Same as insertMany, but with the precondition that the input Foldable is sorted.

  Instances  Collection IntSet Int Int  Collection (IntMap a) (Int, a) (Int, a)  Collection (Seq a) a a  Ord a => Collection (Set a) a a  Ord a => Collection (Set a) a a  Enum a => Collection (Set a) a a  Eq a => Collection (SetList [a]) a a  Collection [a] a a  Ord k => Collection (Map k a) (k, a) (k, a)  Ord k => Collection (Map k a) (k, a) (k, a)  Sequence c (k, v) => Collection (AssocList c k v) (k, v) (k, v)  Collection m (k, v) (k, v) => Collection (ElemsView m k v) (k, v) v  Collection m (k, v) (k, v) => Collection (KeysView m k v) (k, v) k  (Ord k, Sequence s k) => Collection (Trie s k v) (s, v) (s, v) 



class Collection c a a => Collection' c a 


unfold :: Collection c a a => (b > Maybe (a, b)) > b > c 

Map


class Monoid c => Map c k a  c > k a where 
Class of maplike types. (aka. for sparse associative types).
In opposition of Indexed, Map supports unexisting value for some indices.
  Methods  delete :: k > c > c  Remove a key from the keySet (and therefore the associated value in the Map).
  member :: k > c > Bool  Tells whether an key is member of the keySet.
  union :: c > c > c  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 > c  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 > c  Difference of two keySets.
Difference is to be read infix: a difference b returns a set containing the
elements of a that are also absent from b.
  isSubset :: c > c > Bool  s1 isSubset s2 returns True iff. the keys in s1 form a subset of the keys in s2.
  lookup :: Monad m => k > c > m a  Lookup the value at a given key.
  alter :: (Maybe a > Maybe a) > k > c > c  Change the value associated to a given key. Nothing represents no associated value.
  insertWith :: (a > a > a) > k > a > c > c  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 > c  Convert a Foldable to a Map, with a combining function.
  mapWithKey :: (k > a > a) > c > c  Apply a function over all values in the map.
  unionWith :: (a > a > a) > c > c > c  Union with a combining function.
  intersectionWith :: (a > a > a) > c > c > c  Intersection with a combining function.
  differenceWith :: (a > a > Maybe a) > c > c > c  Difference with a combining function.
  isSubmapBy :: (a > a > Bool) > c > c > Bool  isSubmapBy

  Instances  


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


unionsWith :: (Collection s i o, Map s k a, Foldable cs s) => (a > a > a) > cs > s 
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 c 
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 c 
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 b 

(!) :: Indexed c k v => c > k > v 
Infix version of index, with arguments swapped.


Set


class Map c k () => Set c k  c > k where 
Class for setlike collection types. A set is really a map
with no value associated to the keys,
so Set just states so.
  Methods  haddock_candy :: c > k  Dummy method for haddock to accept the class.

  Instances  


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


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


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


Sequence


class (Monoid c, Collection c a a) => Sequence c a where 
Class of sequentialaccess types.
In addition of the Collection services, it provides deconstruction and concatenation.
  Methods  take :: Int > c > c  The first i elements of a sequence.
  drop :: Int > c > c  Elements of a sequence after the first i.
  splitAt :: Int > c > (c, c)  Split a sequence at a given index.
  reverse :: c > c  Reverse a sequence.
  front :: Monad m => c > m (a, c)  Analyse the left end of a sequence.
  back :: Monad m => c > m (c, a)  Analyse the right end of a sequence.
  cons :: a > c > c  Add an element to the left end of a sequence.
  snoc :: c > a > c  Add an element to the right end of a sequence.
  isPrefix :: Eq a => c > c > Bool  The isPrefix function takes two seqences and returns True iff
the first is a prefix of the second.

  Instances  


head :: Sequence s a => s > a 

tail :: Sequence s a => s > s 

find :: Foldable t a => (a > Bool) > t > Maybe a 
The find function takes a predicate and a structure and returns
the leftmost element of the structure matching the predicate, or
Nothing if there is no such element.


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


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


concatMap :: (Sequence s b, Foldable t a) => (a > s) > t > s 

(<) :: Sequence c i => i > c > c 
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 > c 
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.


(><) :: Sequence c a => c > c > c 
Infix verion of append. Concatenate two sequences.


Others


class (Ix k, Foldable c (k, v), Indexed c k v) => Array c k v  c > k v where 
 Methods  bounds :: c > (k, k)  if (l,r) = bounds c, then inDomain k c == l <= k <= r
  array :: Foldable l (k, v) => (k, k) > l > c  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.

  Instances  


class Indexed c k v  c > k v where 
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.
  Methods  index :: k > c > v  index c k returns element associated to k
  adjust :: (v > v) > k > c > c  adjust f k c applies f to element associated to k and returns the resulting collection.
  inDomain :: k > c > Bool  if inDomain k c, then index c k is guaranteed not to fail.
  (//) :: Foldable l (k, v) => c > l > c  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 > c  accum f takes an array and an association list and accumulates
pairs from the list into the array with the accumulating function f.
Thus accumArray can be defined using accum:

  Instances  


Conversions


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


fromAscFoldable :: (Foldable f a, Collection c' a a) => f > c' 
Conversion from a Foldable to a Collection, with the precondition that the input is sorted.


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


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


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


Views


newtype KeysView m k v 
View to the keys of a dictionnary
 Constructors   Instances  


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


withKeys :: Collection m (k, v) (k, v) => T (KeysView m k v) > T m 

withElems :: Collection m (k, v) (k, v) => T (ElemsView m k v) > T m 

Foldable


module Data.Collections.Foldable 

Concrete collection types


Seq 

IntMap 

IntSet 

type StdSet = Set 

type StdMap = Map 

type AvlSet = Set 

type AvlMap = Map 

Produced by Haddock version 0.7 