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 `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 -- type can be inferred. example :: Key x String -> Key x1 Double -> Key x2 Bool -> String example name salary female = format a ++ "\n" ++ format b ++ "\n" 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) keyLocal :: String keyLocal = withKey $ withKey $ withKey example keyGlobal :: IO String keyGlobal = do name <- createKey salary <- createKey female <- createKey return $ example name salary female main = do print "local" putStr keyLocal print "global" keyGlobal >>= putStr

Which gives:

"local" Edsger: salary=4450.0, female=False Ada: salary=5000.0, female=True "global" Edsger: salary=4450.0, female=False Ada: salary=5000.0, female=True

Key types carry two type arguments: the scope of the key and
the the type of things that can be stored at this key, for example `String`

or `Int`

.

The scope of the key depends on how it is created:

- In the
`keyLocal`

example, keys are created*locally*with the`withKey`

function. The type of the`withKey`

function is`(forall x. Key x a -> b) -> b`

, which means it assigns a key and passes it to the given function. The key cannot escape the function (this would yield a type error). Hence, we say the key is*scoped*to the function. The scope type argument of the key is then an existential type. - In the
`keyGlobal`

example, keys are created*globally*with`createKey`

in the IO monad. This allows to create keys that are not not scoped to a single function, but to the whole program. The scope type argument of the key is then`T`

.

This module differs from hackage package `hetero-map`

in the following ways:

- Lookup, insertion and updates are
*O(log n)*when using this module, whereas they are*O(n)*when using`hetero-map`

. - With this module we cannot statically ensure that a Heterogenous map
has a some key (i.e. (!) might throw error, like in
`Map`

). With`hetero-map`

it is possible to statically rule out such errors. - The interface of this module is more similar to
`Map`

.

This module differs from `stable-maps`

in the following ways:

- Key can be created safely without using the IO monad.
- The interface is more uniform and implements more of the
`Map`

interface. - This module uses a Hashmap as a backend, whereas
`stable-maps`

uses`Data.Map`

. Hashmaps are faster, see http://blog.johantibell.com/2012/03/announcing-unordered-containers-02.html.

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.HashMap.Lazy`

as a backend. Every function from `Map`

that makes sense in a heterogenous setting has been implemented.

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 s a
- withKey :: (forall x. Key x a -> b) -> b
- data T
- createKey :: IO (Key T a)
- (!) :: 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

The datatype of Keys.

- x
- The scope of this key. This can either be
`T`

for top-level keys created with`createKey`

or an existential type for keys introduced by`withKey`

. - a
- The type of things that can be sorted at this key.

For example, `Key T Int`

is a top-level key that can be used to store values
of type `Int`

in a heterogenous map.

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

union :: HMap -> HMap -> HMapSource

*O(n+m)*.
The expression (

) takes the left-biased union of `union`

t1 t2`t1`

and `t2`

.
It prefers `t1`

when duplicate keys are encountered.

## Difference

difference :: HMap -> HMap -> HMapSource

*O(n+m)*. Difference of two maps.
Return elements of the first map not existing in the second map.

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