Safe Haskell | Trustworthy |
---|

This module provides finite maps that only grow. It is based on the popular Data.Map
balanced-tree representation of maps. Thus scalability is *not* good for this
implementation. However, there are some interoperability benefits. For example,
after running a parallel computation with a map result, this module can produce a
`Map`

in *O(1)* without copying, which may be useful downstream.

- newtype IMap k s v = IMap (LVar s (IORef (Map k v)) (k, v))
- newEmptyMap :: Par e s (IMap k s v)
- newMap :: Map k v -> Par e s (IMap k s v)
- newFromList :: (Ord k, Eq v) => [(k, v)] -> Par e s (IMap k s v)
- insert :: (Ord k, Eq v, HasPut e) => k -> v -> IMap k s v -> Par e s ()
- getKey :: (HasGet e, Ord k) => k -> IMap k s v -> Par e s v
- waitValue :: (Ord k, Eq v, HasGet e) => v -> IMap k s v -> Par e s ()
- waitSize :: HasGet e => Int -> IMap k s v -> Par e s ()
- modify :: forall f a b e s key. (Ord key, LVarData1 f, Show key, Ord a, HasPut e) => IMap key s (f s a) -> key -> Par e s (f s a) -> (f s a -> Par e s b) -> Par e s b
- gmodify :: forall f a b e s key. (Ord key, LVarData1 f, LVarWBottom f, LVContents f a, Show key, Ord a, HasPut e) => IMap key s (f s a) -> key -> (f s a -> Par e s b) -> Par e s b
- getOrInit :: forall f a b e s key. (Ord key, LVarData1 f, LVarWBottom f, LVContents f a, Show key, Ord a, HasPut e) => key -> IMap key s (f s a) -> Par e s (f s a)
- forEach :: IMap k s v -> (k -> v -> Par e s ()) -> Par e s ()
- forEachHP :: Maybe HandlerPool -> IMap k s v -> (k -> v -> Par e s ()) -> Par e s ()
- withCallbacksThenFreeze :: forall k v b s e. (HasPut e, HasGet e, HasFreeze e, Eq b) => IMap k s v -> (k -> v -> Par e s ()) -> Par e s b -> Par e s b
- freezeMap :: HasFreeze e => IMap k s v -> Par e s (Map k v)
- fromIMap :: IMap k Frzn a -> Map k a
- traverseFrzn_ :: Ord k => (k -> a -> Par e s ()) -> IMap k Frzn a -> Par e s ()
- copy :: (Ord k, Eq v, HasPut e) => IMap k s v -> Par e s (IMap k s v)
- traverseMap :: (Ord k, Eq b, HasPut e) => (k -> a -> Par e s b) -> IMap k s a -> Par e s (IMap k s b)
- traverseMap_ :: (Ord k, Eq b, HasPut e) => (k -> a -> Par e s b) -> IMap k s a -> IMap k s b -> Par e s ()
- union :: (Ord k, Eq a, HasPut e) => IMap k s a -> IMap k s a -> Par e s (IMap k s a)
- traverseMapHP :: (Ord k, Eq b, HasPut e) => Maybe HandlerPool -> (k -> a -> Par e s b) -> IMap k s a -> Par e s (IMap k s b)
- traverseMapHP_ :: (Ord k, Eq b, HasPut e) => Maybe HandlerPool -> (k -> a -> Par e s b) -> IMap k s a -> IMap k s b -> Par e s ()
- unionHP :: (Ord k, Eq a, HasPut e) => Maybe HandlerPool -> IMap k s a -> IMap k s a -> Par e s (IMap k s a)

# Basic operations

newtype IMap k s v

The map datatype itself. Like all other LVars, it has an `s`

parameter (think
`STRef`

) in addition to the `a`

parameter that describes the type of elements
in the set.

Performance note: There is only *one* mutable location in this implementation. Thus
it is not a scalable implementation.

LVarData1 (IMap k) | An |

OrderedLVarData1 (IMap k) | The |

Foldable (IMap k Trvrsbl) | |

Foldable (IMap k Frzn) | |

Eq (IMap k s v) | Equality is physical equality, as with |

(Show k, Show a) => Show (IMap k Trvrsbl a) | For convenience only; the user could define this. |

(Show k, Show a) => Show (IMap k Frzn a) | |

Generator (IMap k Frzn a) | |

DeepFrz a => DeepFrz (IMap k s a) |

newEmptyMap :: Par e s (IMap k s v)

Create a fresh map with nothing in it.

newFromList :: (Ord k, Eq v) => [(k, v)] -> Par e s (IMap k s v)

insert :: (Ord k, Eq v, HasPut e) => k -> v -> IMap k s v -> Par e s ()

Put a single entry into the map. Strict (WHNF) in the key and value.

As with other container LVars, if a key is inserted multiple times, the values had
better be equal `(==)`

, or a multiple-put error is raised.

getKey :: (HasGet e, Ord k) => k -> IMap k s v -> Par e s v

Wait for the map to contain a specified key, and return the associated value.

waitValue :: (Ord k, Eq v, HasGet e) => v -> IMap k s v -> Par e s ()

Wait until the map contains a certain value (on any key).

waitSize :: HasGet e => Int -> IMap k s v -> Par e s ()

Wait on the *size* of the map, not its contents.

:: forall f a b e s key . (Ord key, LVarData1 f, Show key, Ord a, HasPut e) | |

=> IMap key s (f s a) | |

-> key | The key to lookup. |

-> Par e s (f s a) | Create a new "bottom" element whenever an entry is not present. |

-> (f s a -> Par e s b) | The computation to apply on the right-hand side of the keyed entry. |

-> Par e s b |

`IMap`

s containing other LVars have some additional capabilities compared to
those containing regular Haskell data. In particular, it is possible to modify
existing entries (monotonically). Further, this `modify`

function implicitly
inserts a "bottom" element if there is no existing entry for the key.

Unfortunately, that means that this takes another computation for creating new
"bottom" elements for the nested LVars stored inside the `IMap`

.

# Generic routines and convenient aliases

:: forall f a b e s key . (Ord key, LVarData1 f, LVarWBottom f, LVContents f a, Show key, Ord a, HasPut e) | |

=> IMap key s (f s a) | |

-> key | The key to lookup. |

-> (f s a -> Par e s b) | The computation to apply on the right-hand side of the keyed entry. |

-> Par e s b |

getOrInit :: forall f a b e s key. (Ord key, LVarData1 f, LVarWBottom f, LVContents f a, Show key, Ord a, HasPut e) => key -> IMap key s (f s a) -> Par e s (f s a)

Return the preexisting value for a key if it exists, and otherwise return

This is a convenience routine that can easily be defined in terms of `gmodify`

# Iteration and callbacks

forEach :: IMap k s v -> (k -> v -> Par e s ()) -> Par e s ()

Add an (asynchronous) callback that listens for all new new key/value pairs added to the map.

:: Maybe HandlerPool | optional pool to enroll in |

-> IMap k s v | Map to listen to |

-> (k -> v -> Par e s ()) | callback |

-> Par e s () |

Add an (asynchronous) callback that listens for all new key/value pairs added to the map, optionally enrolled in a handler pool.

withCallbacksThenFreeze :: forall k v b s e. (HasPut e, HasGet e, HasFreeze e, Eq b) => IMap k s v -> (k -> v -> Par e s ()) -> Par e s b -> Par e s b

Register a per-element callback, then run an action in this context, and freeze when all (recursive) invocations of the callback are complete. Returns the final value of the provided action.

# Quasi-deterministic operations

freezeMap :: HasFreeze e => IMap k s v -> Par e s (Map k v)

Get the exact contents of the map. As with any
quasi-deterministic operation, using `freezeMap`

may cause your
program to exhibit a limited form of nondeterminism: it will never
return the wrong answer, but it may include synchronization bugs
that can (nondeterministically) cause exceptions.

This Data.Map-based implementation has the special property that
you can retrieve the full map without any `IO`

, and without
nondeterminism leaking. (This is because the internal order is
fixed for the tree-based representation of maps that Data.Map
uses.)

fromIMap :: IMap k Frzn a -> Map k a

*O(1)*: Convert from an `IMap`

to a plain `Map`

.
This is only permitted when the `IMap`

has already been frozen.
This is useful for processing the result of `runParThenFreeze`

.

traverseFrzn_ :: Ord k => (k -> a -> Par e s ()) -> IMap k Frzn a -> Par e s ()

Traverse a frozen map for side effect. This is useful (in comparison with more generic operations) because the function passed in may see the key as well as the value.

# Higher-level derived operations

copy :: (Ord k, Eq v, HasPut e) => IMap k s v -> Par e s (IMap k s v)

Return a fresh map which will contain strictly more elements than the input. That is, things put in the former go in the latter, but not vice versa.

traverseMap :: (Ord k, Eq b, HasPut e) => (k -> a -> Par e s b) -> IMap k s a -> Par e s (IMap k s b)

Establish a monotonic map between the input and output sets. Produce a new result based on each element, while leaving the keys the same.

traverseMap_ :: (Ord k, Eq b, HasPut e) => (k -> a -> Par e s b) -> IMap k s a -> IMap k s b -> Par e s ()

An imperative-style, in-place version of `traverseMap`

that takes the output set
as an argument.

union :: (Ord k, Eq a, HasPut e) => IMap k s a -> IMap k s a -> Par e s (IMap k s a)

Return a new map which will (ultimately) contain everything in either input map. Conflicting entries will result in a multiple put exception.

# Alternate versions of derived ops that expose `HandlerPool`

s they create

traverseMapHP :: (Ord k, Eq b, HasPut e) => Maybe HandlerPool -> (k -> a -> Par e s b) -> IMap k s a -> Par e s (IMap k s b)

A variant of `traverseMap`

that optionally ties the handlers to a pool.

traverseMapHP_ :: (Ord k, Eq b, HasPut e) => Maybe HandlerPool -> (k -> a -> Par e s b) -> IMap k s a -> IMap k s b -> Par e s ()

A variant of `traverseMap_`

that optionally ties the handlers to a pool.