Data.LVar.SLSet

This module provides sets that only grow. It is based on a concurrent skip list representation of sets.

This module is usually a more efficient alternative to Data.LVar.PureSet, and provides almost the same interface. However, it's always good to test multiple data structures if you have a performance-critical use case.

Basic operations

data ISet s a

The set 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: this data structure reduces contention between parallel computations inserting into the map, but all blocking computations are not as scalable. All continuations waiting for not-yet-present elements will currently share a single queue [2013.09.26].

Instances

LVarData1 ISet

An ISet can be treated as a generic container LVar.

OrderedLVarData1 ISet

The ISets in this module also have the special property that they support an O(1) freeze operation which immediately yields a Foldable container (snapFreeze).

Foldable (ISet Trvrsbl)

Foldable (ISet Frzn)

Eq (ISet s v)

Physical identity, just as with IORefs.

Show a => Show (ISet Trvrsbl a)

For convenience only; the user could define this.

Show a => Show (ISet Frzn a)

DeepFrz a => DeepFrz (ISet s a)

type FrzType (ISet s a) = ISet Frzn (FrzType a)

newEmptySet :: Ord a => Par d s (ISet s a)

Create a new, empty, monotonically growing set.

newSet :: Ord a => Set a -> Par d s (ISet s a)

Create a new ISet populated with initial elements.

newFromList :: Ord a => [a] -> Par d s (ISet s a)

A simple convenience function. Create a new ISet drawing initial elements from an existing list.

insert :: Ord a => a -> ISet s a -> Par d s ()

Put a single element in the set. (WHNF) Strict in the element being put in the set.

waitElem :: Ord a => a -> ISet s a -> Par d s ()

Wait for the set to contain a specified element.

waitSize :: Int -> ISet s a -> Par d s ()

Wait on the size of the set, not its contents.

member :: a -> ISet Frzn a -> Bool

Test whether an element is in a frozen image of a set.

Iteration and callbacks

forEach :: ISet s a -> (a -> Par d s ()) -> Par d s ()

Add an (asynchronous) callback that listens for all new elements added to the set.

forEachHP

Arguments

:: Maybe HandlerPool

optional pool to enroll in

-> ISet s a

Set to listen to

-> (a -> Par d s ())

callback

-> Par d s ()

Add an (asynchronous) callback that listens for all new elements added to the set, optionally enrolled in a handler pool.

Quasi-deterministic operations

freezeSetAfter :: ISet s a -> (a -> QPar s ()) -> QPar s ()

Freeze an ISet after a specified callback/handler is done running. This differs from withCallbacksThenFreeze by not taking an additional action to run in the context of the handlers.

(freezeSetAfter s f == withCallbacksThenFreeze s f 'return ()' )

withCallbacksThenFreeze :: Eq b => ISet s a -> (a -> QPar s ()) -> QPar s b -> QPar 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.

Higher-level derived operations

copy :: Ord a => ISet s a -> Par d s (ISet s a)

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

traverseSet :: Ord b => (a -> Par d s b) -> ISet s a -> Par d s (ISet s b)

Establish a monotonic map between the input and output sets.

traverseSet_ :: Ord b => (a -> Par d s b) -> ISet s a -> ISet s b -> Par d s ()

An imperative-style, in-place version of traverseSet that takes the output set as an argument.

union :: Ord a => ISet s a -> ISet s a -> Par d s (ISet s a)

Return a new set which will (ultimately) contain everything in either input set.

intersection :: Ord a => ISet s a -> ISet s a -> Par d s (ISet s a)

Build a new set which will contain the intersection of the two input sets.

cartesianProd :: (Ord a, Ord b) => ISet s a -> ISet s b -> Par d s (ISet s (a, b))

Take the cartesian product of two sets.

cartesianProds :: Ord a => [ISet s a] -> Par d s (ISet s [a])

Take the cartesian product of several sets.

Alternate versions of derived ops that expose HandlerPools they create

traverseSetHP :: Ord b => Maybe HandlerPool -> (a -> Par d s b) -> ISet s a -> Par d s (ISet s b)

Variant of traverseSet that optionally ties the handlers to a pool.

traverseSetHP_ :: Ord b => Maybe HandlerPool -> (a -> Par d s b) -> ISet s a -> ISet s b -> Par d s ()

Variant of traverseSet_ that optionally ties the handlers to a pool.

cartesianProdHP :: (Ord a, Ord b) => Maybe HandlerPool -> ISet s a -> ISet s b -> Par d s (ISet s (a, b))

Variant of cartesianProd that optionally ties the handlers to a pool.

cartesianProdsHP :: Ord a => Maybe HandlerPool -> [ISet s a] -> Par d s (ISet s [a])

Variant of cartesianProds that optionally ties the handlers to a pool.