Haskell Hierarchical Libraries (collections package)ContentsIndex
Data.Collections
PortabilityMPTC, FD, undecidable instances
Stabilityexperimental
Maintainerjeanphilippe.bernardy; google mail.
Contents
Classes
Collection
Map
Set
Sequence
Others
Conversions
Views
Foldable
Concrete collection types
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 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 qualified.

Synopsis
class Foldable c o => Collection c i o | c -> i o where
empty :: c
isSingleton :: c -> Bool
filter :: (o -> Bool) -> c -> c
insert :: i -> c -> c
singleton :: i -> c
insertMany :: Foldable c' i => c' -> c -> c
insertManySorted :: Foldable c' i => c' -> c -> c
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
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
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 :: (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
haddock_candy :: c -> k
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
take :: Int -> c -> c
drop :: Int -> c -> c
splitAt :: Int -> c -> (c, c)
reverse :: c -> c
front :: Monad m => c -> m (a, c)
back :: Monad m => c -> m (c, a)
cons :: a -> c -> c
snoc :: c -> a -> c
isPrefix :: Eq a => c -> c -> Bool
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
bounds :: c -> (k, k)
array :: Foldable l (k, v) => (k, k) -> l -> c
class Indexed c k v | c -> k v where
index :: k -> c -> v
adjust :: (v -> v) -> k -> c -> c
inDomain :: k -> c -> Bool
(//) :: Foldable l (k, v) => c -> l -> c
accum :: Foldable l (k, v') => (v -> v' -> v) -> c -> l -> c
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 {
fromKeysView :: m
}
newtype ElemsView m k v = ElemsView {
fromElemsView :: m
}
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.
show/hide 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 map-like 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
show/hide Instances
Map IntSet Int ()
Map (IntMap a) Int a
Ord a => Map (Set a) a ()
Ord a => Map (Set a) a ()
Enum a => Map (Set a) a ()
Eq a => Map (SetList [a]) a ()
Ord k => Map (Map k a) k a
Ord k => Map (Map k a) k a
(Eq k, Sequence c (k, v), Monoid (AssocList c k v)) => Map (AssocList c k v) k v
Map m k v => Map (KeysView m k v) k v
(Ord k, Sequence s k) => Map (Trie s k v) s v
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 set-like 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.
show/hide Instances
Set IntSet Int
Ord a => Set (Set a) a
Ord a => Set (Set a) a
Enum a => Set (Set a) a
Eq a => Set (SetList [a]) a
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 sequential-access 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.
show/hide Instances
Sequence (Seq a) a
Sequence [a] a
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!(i-1)) | 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 array-bounds error, but bounds still yields the bounds with which the array was constructed.

show/hide Instances
Ix i => Array (Array i e) i e
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 1-origin, 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:
show/hide Instances
Indexed (IntMap a) Int a
Indexed (Seq a) Int a
Indexed [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 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
KeysView
fromKeysView :: m
show/hide Instances
(Monoid m, Map m k v) => Monoid (KeysView m k v)
Foldable m (k, v) => Foldable (KeysView m k v) k
Collection m (k, v) (k, v) => Collection (KeysView m k v) (k, v) k
Map m k v => Map (KeysView m k v) k v
newtype ElemsView m k v
View to the elements of a dictionnary
Constructors
ElemsView
fromElemsView :: m
show/hide Instances
Foldable m (k, v) => Foldable (ElemsView m k v) v
Collection m (k, v) (k, v) => Collection (ElemsView m k v) (k, v) v
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