Portability | portable |
---|---|

Stability | experimental |

Maintainer | exclipy@gmail.com |

An implementation of maps from keys to values (dictionaries) based on the hash array mapped trie.

Since many function names (but not the type name) clash with
Prelude names, this module is usually imported `qualified`

, e.g.

import qualified Data.HamtMap as HM

This data structure is based on Phil Bagwell's hash array mapped trie, which is described by his original paper:

- data Eq k => HamtMap k v
- (!) :: Eq k => HamtMap k v -> k -> v
- member :: Eq k => k -> HamtMap k v -> Bool
- notMember :: Eq k => k -> HamtMap k v -> Bool
- lookup :: Eq k => k -> HamtMap k v -> Maybe v
- empty :: Eq k => (k -> Int32) -> HamtMap k v
- singleton :: Eq k => (k -> Int32) -> k -> v -> HamtMap k v
- insert :: Eq k => k -> v -> HamtMap k v -> HamtMap k v
- insertWith :: Eq k => (v -> v -> v) -> k -> v -> HamtMap k v -> HamtMap k v
- delete :: Eq k => k -> HamtMap k v -> HamtMap k v
- adjust :: Eq k => (v -> v) -> k -> HamtMap k v -> HamtMap k v
- update :: Eq k => (v -> Maybe v) -> k -> HamtMap k v -> HamtMap k v
- alter :: Eq k => (Maybe v -> Maybe v) -> k -> HamtMap k v -> HamtMap k v
- map :: Eq k => (v -> v) -> HamtMap k v -> HamtMap k v
- mapWithKey :: Eq k => (k -> v -> v) -> HamtMap k v -> HamtMap k v
- elems :: Eq k => HamtMap k v -> [v]
- keys :: Eq k => HamtMap k v -> [k]
- toList :: Eq k => HamtMap k v -> [(k, v)]
- fromListWith :: Eq k => (k -> Int32) -> (v -> v -> v) -> [(k, v)] -> HamtMap k v
- fromList :: Eq k => (k -> Int32) -> [(k, v)] -> HamtMap k v

# HamtMap type

# Operators

(!) :: Eq k => HamtMap k v -> k -> vSource

Find the value at a key.
Calls `error`

when the element can not be found.

# Query

# Construction

empty :: Eq k => (k -> Int32) -> HamtMap k vSource

`(`

is the empty HamtMap, with hashFn being the key hash function.
`empty`

hashFn)

singleton :: Eq k => (k -> Int32) -> k -> v -> HamtMap k vSource

`(`

is a single-element HamtMap holding `singleton`

hashFn key value)`(key, value)`

# Insertion

insert :: Eq k => k -> v -> HamtMap k v -> HamtMap k vSource

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 :: Eq k => (v -> v -> v) -> k -> v -> HamtMap k v -> HamtMap k vSource

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 :: Eq k => k -> HamtMap k v -> HamtMap k vSource

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 :: Eq k => (v -> v) -> k -> HamtMap k v -> HamtMap k vSource

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.

# Traversal

map :: Eq k => (v -> v) -> HamtMap k v -> HamtMap k vSource

Map a function over all values in the map.

mapWithKey :: Eq k => (k -> v -> v) -> HamtMap k v -> HamtMap k vSource

Map a function over all values in the map.

# Conversion

fromListWith :: Eq k => (k -> Int32) -> (v -> v -> v) -> [(k, v)] -> HamtMap k vSource

Build a map from a list of key/value pairs with a combining function.