Portability | portable |
---|---|
Stability | provisional |
Maintainer | atzeus@gmail.org |
Safe Haskell | None |
An efficient implementation of heterogeneous maps.
A heterogeneous map can store values of different types. This in contrast to a homogenous map (such as the one in Data.Map) which can store values of a single type.
For example, here we use
a map with String
(name), Double
(salary) and Bool
(female):
import Data.HMap example name salary female = do putStrLn $ format a putStrLn $ format b where a = insert name "Edsger" $ insert salary 4450.0 $ insert female False empty b = insert name "Ada" $ insert salary 5000.0 $ insert female True empty format x = x ! name ++ ": salary=" ++ show (x ! salary) ++ ", female=" ++ show (x ! female) main = withKey $ withKey $ withKey example
The output of this program:
Edsger: salary=4450.0, female=False Ada: salary=5000.0, female=True
The module differes from HeteroMap.Map in the following ways:
- Lookup, insertion and updates are O(log n) when using this module, whereas they are O(n) when using HeteroMap.Map
- With this module we cannot statically ensure that a Heterogenous map has a some key (i.e. (!) might throw error, like in Data.Map). With HeteroMap.Map it is possible to statically rule out such errors.
- The interface of this module is more similar to Data.Map
Since many function names (but not the type name) clash with
Prelude names, this module is usually imported qualified
, e.g.
import Data.HMap (HMap) import qualified Data.HMap as HMap
This module uses Data.Map as a backend.
Note that the implementation is left-biased -- the elements of a
first argument are always preferred to the second, for example in
union
or insert
.
Operation comments contain the operation time complexity in the Big-O notation http://en.wikipedia.org/wiki/Big_O_notation.
- data HMap
- data Key x a
- withKey :: (forall x. Key x a -> b) -> b
- (!) :: HMap -> Key x a -> a
- (\\) :: HMap -> HMap -> HMap
- null :: HMap -> Bool
- size :: HMap -> Int
- member :: Key x a -> HMap -> Bool
- notMember :: Key x a -> HMap -> Bool
- lookup :: Key x a -> HMap -> Maybe a
- findWithDefault :: a -> Key x a -> HMap -> a
- empty :: HMap
- singleton :: Key x a -> a -> HMap
- insert :: Key x a -> a -> HMap -> HMap
- insertWith :: (a -> a -> a) -> Key x a -> a -> HMap -> HMap
- delete :: Key x a -> HMap -> HMap
- adjust :: (a -> a) -> Key x a -> HMap -> HMap
- update :: (a -> Maybe a) -> Key x a -> HMap -> HMap
- alter :: (Maybe a -> Maybe a) -> Key x a -> HMap -> HMap
- union :: HMap -> HMap -> HMap
- unions :: [HMap] -> HMap
- difference :: HMap -> HMap -> HMap
- intersection :: HMap -> HMap -> HMap
HMap type
Keys
withKey :: (forall x. Key x a -> b) -> bSource
O(1). Scopes a key to the given function The key cannot escape the function (because of the existential type).
The implementation actually *creates* a key, but because the key cannot escape
the given function f
, there is no way to observe that if we run
withKey f
twice, that it will get a different key the second time.
Operators
(!) :: HMap -> Key x a -> aSource
O(log n). Find the value at a key.
Calls error
when the element can not be found.
Query
member :: Key x a -> HMap -> BoolSource
O(log n). Is the key a member of the map? See also notMember
.
notMember :: Key x a -> HMap -> BoolSource
O(log n). Is the key not a member of the map? See also member
.
findWithDefault :: a -> Key x a -> HMap -> aSource
O(log n). The expression (
returns
the value at key findWithDefault
def k map)k
or returns default value def
when the key is not in the map.
Construction
Insertion
insert :: Key x a -> a -> HMap -> HMapSource
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. insert
is equivalent to
.
insertWith
const
insertWith :: (a -> a -> a) -> Key x a -> a -> HMap -> HMapSource
O(log n). Insert with a function, combining new value and old value.
will insert the pair (key, value) into insertWith
f key value mpmp
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)
.
Delete/Update
delete :: Key x a -> HMap -> HMapSource
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 :: (a -> a) -> Key x a -> HMap -> HMapSource
O(log n). Update a value at a specific key with the result of the provided function. When the key is not a member of the map, the original map is returned.
Combine
Union
Difference
difference :: HMap -> HMap -> HMapSource
O(n+m). Difference of two maps.
Return elements of the first map not existing in the second map.
The implementation (from Map
) uses an efficient hedge algorithm comparable with hedge-union.
Intersection
intersection :: HMap -> HMap -> HMapSource
O(n+m). Intersection of two maps. Return data in the first map for the keys existing in both maps.