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 mp`mp`

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.