Safe Haskell	None
Language	Haskell2010

Mikan.Utils.AssocList

Contents

Queries
Updates
Traversals
Conversion

Description

Additional functions for association lists.

WARNING

The functions in this module have terrible asymptotics and terrible constant factors too. New code should not use the functions from this module; consider using Data.Map.Strict or Data.IntMap.Strict.

Synopsis

type AssocList k v = [(k, v)]
lookup :: Eq a => a -> [(a, b)] -> Maybe b
apply :: Ord k => AssocList k v -> k -> Maybe v
insert :: k -> v -> AssocList k v -> AssocList k v
update :: Eq k => k -> v -> AssocList k v -> AssocList k v
updateAt :: Eq k => k -> (v -> v) -> AssocList k v -> AssocList k v
delete :: Eq k => k -> AssocList k v -> AssocList k v
mapWithKey :: (k -> v -> v) -> AssocList k v -> AssocList k v
mapWithKeyM :: Applicative m => (k -> v -> m v) -> AssocList k v -> m (AssocList k v)
mapKeysMonotonic :: (k -> k') -> AssocList k v -> AssocList k' v
keys :: AssocList k v -> [k]

Documentation

type AssocList k v = [(k, v)] Source #

A finite map, represented as a set of pairs.

Invariant: at most one value per key.

Queries

lookup :: Eq a => a -> [(a, b)] -> Maybe b #

\(\mathcal{O}(n)\). lookup key assocs looks up a key in an association list. For the result to be Nothing, the list must be finite.

Examples

Expand

>>> lookup 2 []
Nothing

>>> lookup 2 [(1, "first")]
Nothing

>>> lookup 2 [(1, "first"), (2, "second"), (3, "third")]
Just "second"

apply :: Ord k => AssocList k v -> k -> Maybe v Source #

Lookup keys in the same association list often. Use partially applied to create partial function apply m :: k -> Maybe v.

First time: \(\mathcal{O}(n \log n)\) in the worst case.
Subsequently: \(\mathcal{O}(\log n)\).

Specification: apply m == (lookup m).

Updates

insert :: k -> v -> AssocList k v -> AssocList k v Source #

\(\mathcal{O}(1)\). Add a new binding. Assumes the binding is not yet in the list.

update :: Eq k => k -> v -> AssocList k v -> AssocList k v Source #

\(\mathcal{O}(n)\). Update the value at a key. The key must be in the domain of the finite map. Otherwise, an internal error is raised.

updateAt :: Eq k => k -> (v -> v) -> AssocList k v -> AssocList k v Source #

\(\mathcal{O}(n)\). Update the value at a key with a certain function. The key must be in the domain of the finite map. Otherwise, an internal error is raised.

delete :: Eq k => k -> AssocList k v -> AssocList k v Source #

\(\mathcal{O}(n)\). Delete a binding. The key must be in the domain of the finite map. Otherwise, an internal error is raised.

Traversals

mapWithKey :: (k -> v -> v) -> AssocList k v -> AssocList k v Source #

\(\mathcal{O}(n)\). Map over an association list, preserving the order.

mapWithKeyM :: Applicative m => (k -> v -> m v) -> AssocList k v -> m (AssocList k v) Source #

\(\mathcal{O}(n)\). If called with a effect-producing function, violation of the invariant could matter here (duplicating effects).

mapKeysMonotonic :: (k -> k') -> AssocList k v -> AssocList k' v Source #

\(\mathcal{O}(n)\). Named in analogy to mapKeysMonotonic. To preserve the invariant, it is sufficient that the key transformation is injective (rather than monotonic).

Conversion

keys :: AssocList k v -> [k] Source #

\(\mathcal{O}(n)\). Get the domain (list of keys) of the finite map.