| Copyright | (c) Edward Kmett 2015 |
|---|---|
| License | BSD-style |
| Maintainer | Edward Kmett <ekmett@gmail.com> |
| Portability | non-portable |
| Safe Haskell | Trustworthy |
| Language | Haskell2010 |
Data.Transient.WordMap
Description
This module suppose a Word64-based array-mapped PATRICIA Trie.
The most significant nybble is isolated by using techniques based on https://www.fpcomplete.com/user/edwardk/revisiting-matrix-multiplication/part-4 but modified to work nybble-by-nybble rather than bit-by-bit.
This structure secretly maintains a finger to the previous mutation to speed access and repeated operations.
In addition, we support transient access patterns.
- data WordMap a
- data TWordMap s a
- transient :: WordMap a -> TWordMap s a
- persistent :: PrimMonad m => TWordMap (PrimState m) a -> m (WordMap a)
- modify :: (forall s. TWordMap s a -> ST s (TWordMap s b)) -> WordMap a -> WordMap b
- query :: PrimMonad m => (WordMap a -> r) -> TWordMap (PrimState m) a -> m r
- data MWordMap s a
- thaw :: PrimMonad m => WordMap a -> m (MWordMap (PrimState m) a)
- freeze :: PrimMonad m => MWordMap (PrimState m) a -> m (WordMap a)
- modifyM :: PrimMonad m => (TWordMap (PrimState m) a -> m (TWordMap (PrimState m) a)) -> MWordMap (PrimState m) a -> m ()
- queryM :: PrimMonad m => (WordMap a -> r) -> MWordMap (PrimState m) a -> m r
- singleton :: Word64 -> a -> WordMap a
- empty :: WordMap a
- insert :: Word64 -> a -> WordMap a -> WordMap a
- delete :: Word64 -> WordMap a -> WordMap a
- lookup :: Word64 -> WordMap a -> Maybe a
- focus :: Word64 -> WordMap a -> WordMap a
- trim :: WordMap a -> WordMap a
- fromList :: IsList l => [Item l] -> l
- toList :: IsList l => l -> [Item l]
- singletonT :: Word64 -> a -> TWordMap s a
- emptyT :: TWordMap s a
- insertT :: PrimMonad m => Word64 -> a -> TWordMap (PrimState m) a -> m (TWordMap (PrimState m) a)
- deleteT :: PrimMonad m => Word64 -> TWordMap (PrimState m) a -> m (TWordMap (PrimState m) a)
- lookupT :: PrimMonad m => Word64 -> TWordMap (PrimState m) a -> m (Maybe a)
- focusT :: PrimMonad m => Word64 -> TWordMap (PrimState m) a -> m (TWordMap (PrimState m) a)
- trimT :: PrimMonad m => TWordMap (PrimState m) a -> m (TWordMap (PrimState m) a)
- fromListT :: PrimMonad m => [(Word64, a)] -> m (TWordMap (PrimState m) a)
- toListT :: PrimMonad m => TWordMap (PrimState m) a -> m [(Word64, a)]
- singletonM :: PrimMonad m => Word64 -> a -> m (MWordMap (PrimState m) a)
- emptyM :: PrimMonad m => m (MWordMap (PrimState m) a)
- insertM :: PrimMonad m => Word64 -> a -> MWordMap (PrimState m) a -> m ()
- deleteM :: PrimMonad m => Word64 -> MWordMap (PrimState m) a -> m ()
- lookupM :: PrimMonad m => Word64 -> MWordMap (PrimState m) a -> m (Maybe a)
- focusM :: PrimMonad m => Word64 -> MWordMap (PrimState m) a -> m ()
- trimM :: PrimMonad m => MWordMap (PrimState m) a -> m ()
- fromListM :: PrimMonad m => [(Word64, a)] -> m (MWordMap (PrimState m) a)
- toListM :: PrimMonad m => MWordMap (PrimState m) a -> m [(Word64, a)]
Persistent
Instances
| Functor WordMap Source | |
| Foldable WordMap Source | |
| FunctorWithIndex Word64 WordMap Source | |
| FoldableWithIndex Word64 WordMap Source | |
| IsList (WordMap a) Source | |
| Eq v => Eq (WordMap v) Source | |
| Ord v => Ord (WordMap v) Source | |
| Show a => Show (WordMap a) Source | |
| NFData a => NFData (WordMap a) Source | |
| AsEmpty (WordMap a) Source | |
| Ixed (WordMap a) Source | |
| At (WordMap a) Source | |
| type Item (WordMap a) = (Word64, a) Source | |
| type IxValue (WordMap a) = a Source | |
| type Index (WordMap a) = Word64 Source |
Transient
This is a transient WordMap with a clojure-like API
transient :: WordMap a -> TWordMap s a Source
O(1) worst-case conversion from an immutable structure to a mutable one
persistent :: PrimMonad m => TWordMap (PrimState m) a -> m (WordMap a) Source
O(1) amortized conversion from a mutable structure to an immutable one
modify :: (forall s. TWordMap s a -> ST s (TWordMap s b)) -> WordMap a -> WordMap b Source
Modify an immutable structure with mutable operations.
modify f wm passed f a "persisted" transient that may be reused.
query :: PrimMonad m => (WordMap a -> r) -> TWordMap (PrimState m) a -> m r Source
Query a transient structure with queries designed for an immutable structure.
This does _not_ destroy the transient, although, it does mean subsequent actions need to copy-on-write from scratch.
After query f wm, wm is considered persisted and may be reused.
Mutable
This is a mutable WordMap with a classic Haskell mutable container-style API
On the plus side, this API means you don't need to carefully avoid reusing a transient On the minus side, you have an extra reference to track.
modifyM :: PrimMonad m => (TWordMap (PrimState m) a -> m (TWordMap (PrimState m) a)) -> MWordMap (PrimState m) a -> m () Source
Modify a mutable wordmap with a transient operation.
queryM :: PrimMonad m => (WordMap a -> r) -> MWordMap (PrimState m) a -> m r Source
Query a mutable structure with queries designed for an immutable structure.
Persistent Combinators
trim :: WordMap a -> WordMap a Source
O(1) This function enables us to GC the items that lie on the path to the finger.
Normally we only do this lazily as the finger moves out of a given area, but if you have particularly burdensome items for the garbage collector it may be worth paying this price. to explicitly allow them to go free.
fromList :: IsList l => [Item l] -> l
The fromList function constructs the structure l from the given
list of Item l
toList :: IsList l => l -> [Item l]
The toList function extracts a list of Item l from the structure l.
It should satisfy fromList . toList = id.
Transient Combinators
singletonT :: Word64 -> a -> TWordMap s a Source
insertT :: PrimMonad m => Word64 -> a -> TWordMap (PrimState m) a -> m (TWordMap (PrimState m) a) Source
Transient insert.
insertT k v wm invalidates any unpersisted transient wm it is passed
deleteT :: PrimMonad m => Word64 -> TWordMap (PrimState m) a -> m (TWordMap (PrimState m) a) Source
Transient delete. deleteT k v wm invalidates any unpersisted transient it is passed.
focusT :: PrimMonad m => Word64 -> TWordMap (PrimState m) a -> m (TWordMap (PrimState m) a) Source
This changes the location of the focus in a transient map. Operations near the focus are considerably cheaper.
focusT k wm invalidates any unpersisted transient wm it is passed
Mutable Combinators
singletonM :: PrimMonad m => Word64 -> a -> m (MWordMap (PrimState m) a) Source
focusM :: PrimMonad m => Word64 -> MWordMap (PrimState m) a -> m () Source
This changes the location of the focus in a mutable map. Operations near the focus are considerably cheaper.
trimM :: PrimMonad m => MWordMap (PrimState m) a -> m () Source
O(1) This function enables us to GC the items that lie on the path to the finger.
Normally we only do this lazily as the finger moves out of a given area, but if you have particularly burdensome items for the garbage collector it may be worth paying this price. to explicitly allow them to go free.