Data.Collections

Haskell Hierarchical Libraries (collections package)

Data.Collections

Portability	MPTC, FD, undecidable instances
Stability	experimental
Maintainer	jeanphilippe.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.

Instances

Collection IntSet Int Int

Collection (IntMap a) (Int, a) (Int, a)

Collection (Seq 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)

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

Instances

Map IntSet Int ()

Map (IntMap a) Int 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

(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.

Instances

Set IntSet Int

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.

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.

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:

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, 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'