Data.LVar.PureSet

This module provides sets that only grow. It is based on the popular Data.Set balanced-tree representation of sets. Thus scalability is not good for this implementation. However, there are some interoperability benefits. For exmaple, after running a parallel computation with a set result, this module can produce a Set in O(1) without copying, which may be useful downstream.

Basic operations

newtype ISet s a

The set datatype itself. Like all other LVars, it has an s parameter (like an 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.

Constructors

ISet (LVar s (IORef (Set a)) a)

Instances

LVarData1 ISet

An ISet can be treated as a generic container LVar. However, the polymorphic operations are less useful than the monomorphic ones exposed by this module.

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; 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 :: Par d s (ISet s a)

Create a new, empty, monotonically growing set.

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

Create a new set populated with initial elements.

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

Create a new set 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.

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

pool to enroll in, if any

-> 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.

freezeSet :: ISet s a -> QPar s (Set a)

Get the exact contents of the set. As with any quasi-deterministic operation, using freezeSet 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.Set-based implementation has the special property that you can retrieve the full set without any IO, and without nondeterminism leaking. (This is because the internal order is fixed for the tree-based representation of sets that Data.Set uses.)

fromISet :: ISet Frzn a -> Set a

O(1): Convert from an ISet to a plain Set. This is only permitted when the ISet has already been frozen. This is useful for processing the result of runParThenFreeze.

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.

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

Variant of union that optionally ties the handlers in the resulting set to the same handler pool as those in the two input sets.

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

Variant of intersection that optionally ties the handlers in the resulting set to the same handler pool as those in the two input sets.

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.