Safe Haskell | Trustworthy |
---|

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.

- newtype ISet s a = ISet (LVar s (IORef (Set a)) a)
- newEmptySet :: Par e s (ISet s a)
- newSet :: Set a -> Par e s (ISet s a)
- newFromList :: Ord a => [a] -> Par e s (ISet s a)
- insert :: HasPut e => Ord a => a -> ISet s a -> Par e s ()
- waitElem :: HasGet e => Ord a => a -> ISet s a -> Par e s ()
- waitSize :: HasGet e => Int -> ISet s a -> Par e s ()
- forEach :: ISet s a -> (a -> Par e s ()) -> Par e s ()
- forEachHP :: Maybe HandlerPool -> ISet s a -> (a -> Par e s ()) -> Par e s ()
- freezeSetAfter :: (HasPut e, HasGet e, HasFreeze e) => ISet s a -> (a -> Par e s ()) -> Par e s ()
- withCallbacksThenFreeze :: (HasPut e, HasGet e, HasFreeze e, Eq b) => ISet s a -> (a -> Par e s ()) -> Par e s b -> Par e s b
- freezeSet :: HasFreeze e => ISet s a -> Par e s (Set a)
- fromISet :: Ord a => ISet Frzn a -> Set a
- copy :: (HasPut e, Ord a) => ISet s a -> Par e s (ISet s a)
- traverseSet :: (HasPut e, Ord b) => (a -> Par e s b) -> ISet s a -> Par e s (ISet s b)
- traverseSet_ :: (HasPut e, Ord b) => (a -> Par e s b) -> ISet s a -> ISet s b -> Par e s ()
- union :: (HasPut e, Ord a) => ISet s a -> ISet s a -> Par e s (ISet s a)
- intersection :: (HasPut e, Ord a) => ISet s a -> ISet s a -> Par e s (ISet s a)
- cartesianProd :: (HasPut e, Ord a, Ord b) => ISet s a -> ISet s b -> Par e s (ISet s (a, b))
- cartesianProds :: (HasPut e, Ord a) => [ISet s a] -> Par e s (ISet s [a])
- traverseSetHP :: (HasPut e, Ord b) => Maybe HandlerPool -> (a -> Par e s b) -> ISet s a -> Par e s (ISet s b)
- traverseSetHP_ :: (HasPut e, Ord b) => Maybe HandlerPool -> (a -> Par e s b) -> ISet s a -> ISet s b -> Par e s ()
- unionHP :: (HasPut e, Ord a) => Maybe HandlerPool -> ISet s a -> ISet s a -> Par e s (ISet s a)
- intersectionHP :: (HasPut e, Ord a) => Maybe HandlerPool -> ISet s a -> ISet s a -> Par e s (ISet s a)
- cartesianProdHP :: (HasPut e, Ord a, Ord b) => Maybe HandlerPool -> ISet s a -> ISet s b -> Par e s (ISet s (a, b))
- cartesianProdsHP :: (HasPut e, Ord a) => Maybe HandlerPool -> [ISet s a] -> Par e s (ISet s [a])

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

LVarData1 ISet | An |

OrderedLVarData1 ISet | The |

Foldable (ISet Trvrsbl) | |

Foldable (ISet Frzn) | |

Eq (ISet s v) | Physical identity, just as with |

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

newEmptySet :: Par e s (ISet s a)

Create a new, empty, monotonically growing set.

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

Create a new set drawing initial elements from an existing list.

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

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

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

Wait for the set to contain a specified element.

# Iteration and callbacks

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

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

:: Maybe HandlerPool | pool to enroll in, if any |

-> ISet s a | Set to listen to |

-> (a -> Par e s ()) | callback |

-> Par e s () |

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

# Freezing and quasi-deterministic operations

freezeSetAfter :: (HasPut e, HasGet e, HasFreeze e) => ISet s a -> (a -> Par e s ()) -> Par e 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 :: (HasPut e, HasGet e, HasFreeze e, Eq b) => ISet s a -> (a -> 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.

freezeSet :: HasFreeze e => ISet s a -> Par e 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 :: Ord a => 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 :: (HasPut e, Ord a) => ISet s a -> Par e 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 :: (HasPut e, Ord b) => (a -> Par e s b) -> ISet s a -> Par e s (ISet s b)

Establish a monotonic map between the input and output sets.

traverseSet_ :: (HasPut e, Ord b) => (a -> Par e s b) -> ISet s a -> ISet s b -> Par e s ()

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

that takes the output set
as an argument.

union :: (HasPut e, Ord a) => ISet s a -> ISet s a -> Par e s (ISet s a)

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

intersection :: (HasPut e, Ord a) => ISet s a -> ISet s a -> Par e s (ISet s a)

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

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

Take the cartesian product of two sets.

cartesianProds :: (HasPut e, Ord a) => [ISet s a] -> Par e s (ISet s [a])

Take the cartesian product of several sets.

# Alternate versions of derived ops that expose `HandlerPool`

s they create

traverseSetHP :: (HasPut e, Ord b) => Maybe HandlerPool -> (a -> Par e s b) -> ISet s a -> Par e s (ISet s b)

Variant of `traverseSet`

that optionally ties the handlers to a pool.

traverseSetHP_ :: (HasPut e, Ord b) => Maybe HandlerPool -> (a -> Par e s b) -> ISet s a -> ISet s b -> Par e s ()

Variant of `traverseSet_`

that optionally ties the handlers to a pool.

unionHP :: (HasPut e, Ord a) => Maybe HandlerPool -> ISet s a -> ISet s a -> Par e 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 :: (HasPut e, Ord a) => Maybe HandlerPool -> ISet s a -> ISet s a -> Par e 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 :: (HasPut e, Ord a, Ord b) => Maybe HandlerPool -> ISet s a -> ISet s b -> Par e s (ISet s (a, b))

Variant of `cartesianProd`

that optionally ties the handlers to a pool.

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

Variant of `cartesianProds`

that optionally ties the handlers to a pool.