HashtablesPlus

Data Structures

data Table t k v

A newtype wrapper over a HashTable implementation t.

E.g.:

 type CuckooTable k v = Table Cuckoo k v

Instances

(HashTable t, Key k) => Delete (Table t k v)

(HashTable t, Key k) => Insert (Table t k v)

(HashTable t, Key k) => Elem (Table t k v)

(HashTable t, Key k) => Lookup (Table t k v)

(HashTable t, Key k) => Collection (Table t k v)

data Set t a

A set of values, which have instances for Eq and Hashable.

t is the underlying HashTable implementation, a is the item.

E.g.:

 type CuckooSet a = Set Cuckoo a

Instances

(HashTable t, Key a) => Delete (Set t a)

(HashTable t, Key a) => Insert (Set t a)

(HashTable t, Key a) => Elem (Set t a)

(HashTable t, Key a) => Collection (Set t a)

data HashRefSet t a

A specialized set of HashRefs.

t is the underlying HashTable implementation, a is the item.

E.g.:

 type LinearHashRefSet a = HashRefSet Linear a

Instances

HashTable t => Delete (HashRefSet t a)

HashTable t => Insert (HashRefSet t a)

HashTable t => Elem (HashRefSet t a)

HashTable t => Collection (HashRefSet t a)

data MultiTable t k s

A multitable (or multimap) with underlying HashTable t, key k and a set implementation s.

E.g.:

 type BasicMultiTable k v = MultiTable Basic k (Set Basic v)

If a Sized implementation of set is specified, a more space efficient instance of Delete will be used. E.g.:

 MultiTable Basic k (Sized (Set Basic v))

Instances

(HashTable t, Key k, Delete c) => Delete (MultiTable t k (Sized c))

(HashTable t, Key k, Delete c) => Delete (MultiTable t k c)

(HashTable t, Key k, Insert s) => Insert (MultiTable t k s)

(HashTable t, Key k, Elem s) => Elem (MultiTable t k s)

(HashTable t, Key k, Collection s, ~ * (Value s) (Row s)) => LookupMulti (MultiTable t k s)

(HashTable t, Key k, Collection s) => Collection (MultiTable t k s)

data Sized c

A wrapper over a Collection, which adds null and size functions of O(1) complexity.

E.g.:

 type SizedLinearTable k v = Sized (Table Linear k v)

Instances

Collection c => Null (Sized c)

Collection c => Size (Sized c)

Delete c => Delete (Sized c)

Insert c => Insert (Sized c)

Elem c => Elem (Sized c)

LookupMulti c => LookupMulti (Sized c)

Lookup c => Lookup (Sized c)

Collection c => Collection (Sized c)

(HashTable t, Key k, Delete c) => Delete (MultiTable t k (Sized c))

HashTable Implementations

These are aliases of implementations of a class HashTable, which provide different performance and memory consumption characteristics. They are used as parameters to data structures. For more info refer to the documentation on aliased types.

type Basic = HashTable

type Cuckoo = HashTable

type Linear = HashTable

Interface

type Key k = (Hashable k, Eq k)

A constraint for values usable as hash table key.

type family Row c

A row of a collection. For tables and multitables it's a key-value pair, for sets it's just the item.

type family UniqueKey c

A unique row identifier. For tables it's a key, for multitables it's a key-value pair, for sets it's the item itself.

type family MultiKey c

A non-unique row identifier. For tables and sets there is none, for multitables it's a key.

type family Value c

An item of a collection. For tables and multitables it's a value (from the key-value pair), for sets it's the item.

class Collection c where

Methods

new :: IO c

Create a new collection.

foldM :: c -> r -> (r -> Row c -> IO r) -> IO r

Strictly fold over the rows.

Instances

Collection c => Collection (Sized c)

HashTable t => Collection (HashRefSet t a)

(HashTable t, Key a) => Collection (Set t a)

(HashTable t, Key k, Collection s) => Collection (MultiTable t k s)

(HashTable t, Key k) => Collection (Table t k v)

class Collection c => Lookup c where

Methods

lookup :: c -> UniqueKey c -> IO (Maybe (Value c))

Lookup an item by a unique key.

Instances

Lookup c => Lookup (Sized c)

(HashTable t, Key k) => Lookup (Table t k v)

class Collection c => LookupMulti c where

Methods

lookupMulti :: c -> MultiKey c -> IO [Value c]

Lookup multiple items by a non-unique key.

Instances

LookupMulti c => LookupMulti (Sized c)

(HashTable t, Key k, Collection s, ~ * (Value s) (Row s)) => LookupMulti (MultiTable t k s)

class Collection c => Elem c where

Methods

elem :: c -> UniqueKey c -> IO Bool

Check whether the collection contains a row by the given unique key.

Instances

Elem c => Elem (Sized c)

HashTable t => Elem (HashRefSet t a)

(HashTable t, Key a) => Elem (Set t a)

(HashTable t, Key k, Elem s) => Elem (MultiTable t k s)

(HashTable t, Key k) => Elem (Table t k v)

class Collection c => Insert c where

Methods

insert :: c -> Row c -> IO Bool

Insert a row into a collection.

Returns a boolean signifying whether a new row has been inserted. Note that if a row has been replaced it returns False.

insertFast :: c -> Row c -> IO ()

Same as insert, but avoiding the calculation of the operation result.

Instances

Insert c => Insert (Sized c)

HashTable t => Insert (HashRefSet t a)

(HashTable t, Key a) => Insert (Set t a)

(HashTable t, Key k, Insert s) => Insert (MultiTable t k s)

(HashTable t, Key k) => Insert (Table t k v)

class Collection c => Delete c where

Methods

delete :: c -> UniqueKey c -> IO Bool

Delete a row from a collection by its identifier.

Returns a boolean signifying whether a row has been removed.

deleteFast :: c -> UniqueKey c -> IO ()

Same as delete, but avoiding the calculation of the operation result.

Instances

Delete c => Delete (Sized c)

HashTable t => Delete (HashRefSet t a)

(HashTable t, Key a) => Delete (Set t a)

(HashTable t, Key k, Delete c) => Delete (MultiTable t k (Sized c))

(HashTable t, Key k, Delete c) => Delete (MultiTable t k c)

(HashTable t, Key k) => Delete (Table t k v)

class Collection c => Size c where

Methods

size :: c -> IO Int

O(1). Get the size of a collection.

Instances

Collection c => Size (Sized c)

class Collection c => Null c where

Methods

null :: c -> IO Bool

O(1). Check whether a collection is empty.

Instances

Collection c => Null (Sized c)

forM_ :: Collection c => c -> (Row c -> IO ()) -> IO ()

Traverse thru all the rows of a collection with side effects.

toList :: Collection c => c -> IO [Row c]

O(n). Convert a collection to a list.