Portability  portable 

Stability  provisional 
Maintainer  http://homepages.nildram.co.uk/~ahey/em.png 
This module provides an AVL tree based clone of the base package Data.Map.
There are some differences though..

size
is O(n), not O(1). Consequently, indexed access is disabled.  The showTree and showTreeWith functions are not implemented.
 Some other functions are not yet implemented.
 data Map k a
 (!) :: Ord k => Map k a > k > a
 (\\) :: Ord k => Map k a > Map k b > Map k a
 null :: Map k a > Bool
 size :: Map k a > Int
 member :: Ord k => k > Map k a > Bool
 lookup :: (Monad m, Ord k) => k > Map k a > m a
 findWithDefault :: Ord k => a > k > Map k a > a
 empty :: Map k a
 singleton :: k > a > Map k a
 insert :: Ord k => k > a > Map k a > Map k a
 insertWith :: Ord k => (a > a > a) > k > a > Map k a > Map k a
 insertWithKey :: Ord k => (k > a > a > a) > k > a > Map k a > Map k a
 insertLookupWithKey :: Ord k => (k > a > a > a) > k > a > Map k a > (Maybe a, Map k a)
 delete :: Ord k => k > Map k a > Map k a
 adjust :: Ord k => (a > a) > k > Map k a > Map k a
 alter :: Ord k => (Maybe a > Maybe a) > k > Map k a > Map k a
 adjustWithKey :: Ord k => (k > a > a) > k > Map k a > Map k a
 update :: Ord k => (a > Maybe a) > k > Map k a > Map k a
 updateWithKey :: Ord k => (k > a > Maybe a) > k > Map k a > Map k a
 updateLookupWithKey :: Ord k => (k > a > Maybe a) > k > Map k a > (Maybe a, Map k a)
 union :: Ord k => Map k a > Map k a > Map k a
 unionWith :: Ord k => (a > a > a) > Map k a > Map k a > Map k a
 unionWithKey :: Ord k => (k > a > a > a) > Map k a > Map k a > Map k a
 unions :: Ord k => [Map k a] > Map k a
 unionsWith :: Ord k => (a > a > a) > [Map k a] > Map k a
 difference :: Ord k => Map k a > Map k b > Map k a
 differenceWith :: Ord k => (a > b > Maybe a) > Map k a > Map k b > Map k a
 differenceWithKey :: Ord k => (k > a > b > Maybe a) > Map k a > Map k b > Map k a
 intersection :: Ord k => Map k a > Map k b > Map k a
 intersectionWith :: Ord k => (a > b > c) > Map k a > Map k b > Map k c
 intersectionWithKey :: Ord k => (k > a > b > c) > Map k a > Map k b > Map k c
 map :: (a > b) > Map k a > Map k b
 mapWithKey :: (k > a > b) > Map k a > Map k b
 mapAccum :: Ord k => (a > b > (a, c)) > a > Map k b > (a, Map k c)
 fold :: (a > b > b) > b > Map k a > b
 foldWithKey :: (k > a > b > b) > b > Map k a > b
 elems :: Map k a > [a]
 keys :: Map k a > [k]
 keysSet :: Map k a > Set k
 liftKeysSet :: (k > b) > Set k > Map k b
 assocs :: Map k a > [(k, a)]
 unsafeFromTree :: AVL (k, a) > Map k a
 toTree :: Map k a > AVL (k, a)
 toList :: Map k a > [(k, a)]
 fromList :: Ord k => [(k, a)] > Map k a
 fromListWith :: Ord k => (a > a > a) > [(k, a)] > Map k a
 fromListWithKey :: Ord k => (k > a > a > a) > [(k, a)] > Map k a
 toAscList :: Map k a > [(k, a)]
 fromAscList :: Eq k => [(k, a)] > Map k a
 fromAscListWith :: Eq k => (a > a > a) > [(k, a)] > Map k a
 fromAscListWithKey :: Eq k => (k > a > a > a) > [(k, a)] > Map k a
 fromDistinctAscList :: [(k, a)] > Map k a
 filter :: Ord k => (a > Bool) > Map k a > Map k a
 filterWithKey :: Ord k => (k > a > Bool) > Map k a > Map k a
 partition :: Ord k => (a > Bool) > Map k a > (Map k a, Map k a)
 partitionWithKey :: Ord k => (k > a > Bool) > Map k a > (Map k a, Map k a)
 split :: Ord k => k > Map k a > (Map k a, Map k a)
 splitLookup :: Ord k => k > Map k a > (Map k a, Maybe a, Map k a)
 isSubmapOf :: (Ord k, Eq a) => Map k a > Map k a > Bool
 isSubmapOfBy :: Ord k => (a > b > Bool) > Map k a > Map k b > Bool
 findMin :: Map k a > (k, a)
 findMax :: Map k a > (k, a)
 deleteMin :: Map k a > Map k a
 deleteMax :: Map k a > Map k a
 deleteFindMin :: Map k a > ((k, a), Map k a)
 deleteFindMax :: Map k a > ((k, a), Map k a)
Map type
A Map from keys k
to values a
.
Typeable2 Map  
Functor (Map k)  
Foldable (Map k)  
(Eq k, Eq a) => Eq (Map k a)  
(Ord k, Ord a) => Ord (Map k a)  
(Show k, Show a) => Show (Map k a)  
Ord k => Monoid (Map k a)  
Ord k => Map (Map k a) k a  
Ord k => Indexed (Map k a) k a  
Foldable (Map k a) (k, a)  
Ord k => SortingCollection (Map k a) (k, a)  
Ord k => Unfoldable (Map k a) (k, a)  
Ord k => Collection (Map k a) (k, a) 
Operators
(!) :: Ord k => Map k a > k > aSource
O(log n). Find the value at a key.
Calls error
when the element can not be found.
Query
lookup :: (Monad m, Ord k) => k > Map k a > m aSource
O(log n). Lookup the value at a key in the map.
findWithDefault :: Ord k => a > k > Map k a > aSource
O(log n). The expression (
returns
the value at key findWithDefault
def k map)k
or returns def
when the key is not in the map.
Construction
Insertion
insert :: Ord k => k > a > Map k a > Map k aSource
O(log n). Insert a new key and value in the map.
If the key is already present in the map, the associated value is
replaced with the supplied value, i.e. insert
is equivalent to
.
insertWith
const
insertWith :: Ord k => (a > a > a) > k > a > Map k a > Map k aSource
O(log n). Insert with a combining function.
insertWithKey :: Ord k => (k > a > a > a) > k > a > Map k a > Map k aSource
O(log n). Insert with a combining function.
insertLookupWithKey :: Ord k => (k > a > a > a) > k > a > Map k a > (Maybe a, Map k a)Source
O(log n). The expression (
)
is a pair where the first element is equal to (insertLookupWithKey
f k x map
)
and the second element equal to (lookup
k map
).
insertWithKey
f k x map
TODO: only one traversal. This requires fiddling with AVL.Push.
Delete/Update
delete :: Ord k => k > Map k a > Map k aSource
O(log n). Delete a key and its value from the map. When the key is not a member of the map, the original map is returned.
adjust :: Ord k => (a > a) > k > Map k a > Map k aSource
O(log n). Adjust a value at a specific key. When the key is not a member of the map, the original map is returned.
adjustWithKey :: Ord k => (k > a > a) > k > Map k a > Map k aSource
O(log n). Adjust a value at a specific key. When the key is not a member of the map, the original map is returned.
updateWithKey :: Ord k => (k > a > Maybe a) > k > Map k a > Map k aSource
O(log n). The expression (
) updates the
value updateWithKey
f k mapx
at k
(if it is in the map). If (f k x
) is Nothing
,
the element is deleted. If it is (
), the key Just
yk
is bound
to the new value y
.
updateLookupWithKey :: Ord k => (k > a > Maybe a) > k > Map k a > (Maybe a, Map k a)Source
O(log n). Lookup and update.
TODO: only one traversal. This requires fiddling with AVL.Push.
Combine
Union
unionWith :: Ord k => (a > a > a) > Map k a > Map k a > Map k aSource
O(n+m). Union with a combining function.
unionWithKey :: Ord k => (k > a > a > a) > Map k a > Map k a > Map k aSource
O(n+m). Union with a combining function.
unionsWith :: Ord k => (a > a > a) > [Map k a] > Map k aSource
The union of a list of maps, with a combining operation:
(
).
unionsWith
f == Prelude.foldl
(unionWith
f) empty
Difference
differenceWith :: Ord k => (a > b > Maybe a) > Map k a > Map k b > Map k aSource
O(n+m). Difference with a combining function.
Intersection
intersection :: Ord k => Map k a > Map k b > Map k aSource
O(n+m). Intersection of two maps. The values in the first
map are returned, i.e.
(
).
intersection
m1 m2 == intersectionWith
const
m1 m2
intersectionWith :: Ord k => (a > b > c) > Map k a > Map k b > Map k cSource
O(n+m). Intersection with a combining function.
intersectionWithKey :: Ord k => (k > a > b > c) > Map k a > Map k b > Map k cSource
O(n+m). Intersection with a combining function.
Intersection is more efficient on (bigset intersection
smallset)
Traversal
Map
mapWithKey :: (k > a > b) > Map k a > Map k bSource
O(n). Map a function over all values in the map.
mapAccum :: Ord k => (a > b > (a, c)) > a > Map k b > (a, Map k c)Source
O(n). The function mapAccum
threads an accumulating
argument through the map in ascending order of keys.
Fold
foldWithKey :: (k > a > b > b) > b > Map k a > bSource
Conversion
liftKeysSet :: (k > b) > Set k > Map k bSource
O(n). Apply a function to each element of a set and return the resulting map.
unsafeFromTree :: AVL (k, a) > Map k aSource
O(1). Convert a sorted AVL tree to an AVL tree based Set (as provided by this module). This function does not check the input AVL tree is sorted.
toTree :: Map k a > AVL (k, a)Source
O(1). Convert an AVL tree based Set (as provided by this module) to a sorted AVL tree.
fromListWith :: Ord k => (a > a > a) > [(k, a)] > Map k aSource
O(n*log n). Build a map from a list of key/value pairs with a combining function. See also fromAscListWith
.
fromListWithKey :: Ord k => (k > a > a > a) > [(k, a)] > Map k aSource
O(n*log n). Build a map from a list of key/value pairs with a combining function. See also fromAscListWithKey
.
Ordered lists
fromAscList :: Eq k => [(k, a)] > Map k aSource
O(n). Build a map from an ascending list in linear time. The precondition (input list is ascending) is not checked.
fromAscListWith :: Eq k => (a > a > a) > [(k, a)] > Map k aSource
O(n). Build a map from an ascending list in linear time with a combining function for equal keys. The precondition (input list is ascending) is not checked.
fromAscListWithKey :: Eq k => (k > a > a > a) > [(k, a)] > Map k aSource
O(n). Build a map from an ascending list in linear time with a combining function for equal keys. The precondition (input list is ascending) is not checked.
fromDistinctAscList :: [(k, a)] > Map k aSource
O(n). Build a map from an ascending list of distinct elements in linear time. The precondition is not checked.
Filter
filter :: Ord k => (a > Bool) > Map k a > Map k aSource
O(n). Filter all values that satisfy the predicate.
filterWithKey :: Ord k => (k > a > Bool) > Map k a > Map k aSource
O(n). Filter all keys/values that satisfy the predicate.
partition :: Ord k => (a > Bool) > Map k a > (Map k a, Map k a)Source
O(n). partition the map according to a predicate. The first map contains all elements that satisfy the predicate, the second all elements that fail the predicate.
partitionWithKey :: Ord k => (k > a > Bool) > Map k a > (Map k a, Map k a)Source
O(n). partition the map according to a predicate. The first map contains all elements that satisfy the predicate, the second all elements that fail the predicate.
split :: Ord k => k > Map k a > (Map k a, Map k a)Source
O(log n). The expression (
) is a pair split
x set(set1,set2)
where all elements in set1
are lower than x
and all elements in
set2
larger than x
. x
is not found in neither set1
nor set2
.
splitLookup :: Ord k => k > Map k a > (Map k a, Maybe a, Map k a)Source
O(log n). The expression (
) splits a map just
like splitLookup
k mapsplit
but also returns
.
lookup
k map
Submap
isSubmapOf :: (Ord k, Eq a) => Map k a > Map k a > BoolSource
O(n+m).
This function is defined as (
).
isSubmapOf
= isSubmapOfBy
(==)
isSubmapOfBy :: Ord k => (a > b > Bool) > Map k a > Map k b > BoolSource
O(n+m).
The expression (
) returns isSubmapOfBy
f t1 t2True
if
all keys in t1
are in tree t2
, and when f
returns True
when
applied to their respective values. For example, the following
expressions are all True
:
isSubmapOfBy (==) (fromList [('a',1)]) (fromList [('a',1),('b',2)]) isSubmapOfBy (<=) (fromList [('a',1)]) (fromList [('a',1),('b',2)]) isSubmapOfBy (==) (fromList [('a',1),('b',2)]) (fromList [('a',1),('b',2)])
But the following are all False
:
isSubmapOfBy (==) (fromList [('a',2)]) (fromList [('a',1),('b',2)]) isSubmapOfBy (<) (fromList [('a',1)]) (fromList [('a',1),('b',2)]) isSubmapOfBy (==) (fromList [('a',1),('b',2)]) (fromList [('a',1)])
Indexed
Min/Max
deleteFindMin :: Map k a > ((k, a), Map k a)Source
O(log n). Delete and find the minimal element.
deleteFindMax :: Map k a > ((k, a), Map k a)Source
O(log n). Delete and find the maximal element.