Data.Concurrent.Deque.Class
Contents
Description
An abstract, parameterizable interface for queues.
This interface includes a non-associated type family for Deques plus separate type classes encapusulating the Deque operations. This design strives to hide the extra phantom-type parameters from the Class constraints and therefore from the type signatures of client code.
- type family Deque lThreaded rThreaded lDbl rDbl bnd safe elt
- data Threadsafe
- data Nonthreadsafe
- data SingleEnd
- data DoubleEnd
- data Bound
- data Grow
- data Safe
- data Dup
- type S = SingleEnd
- type D = DoubleEnd
- type NT = Nonthreadsafe
- type T = Threadsafe
- type Queue a = Deque Nonthreadsafe Nonthreadsafe SingleEnd SingleEnd Grow Safe a
- type ConcQueue a = Deque Threadsafe Threadsafe SingleEnd SingleEnd Grow Safe a
- type ConcDeque a = Deque Threadsafe Threadsafe DoubleEnd DoubleEnd Grow Safe a
- type WSDeque a = Deque Nonthreadsafe Threadsafe DoubleEnd SingleEnd Grow Safe a
- class DequeClass d where
- class DequeClass d => PopL d where
- class DequeClass d => PushR d where
- class DequeClass d => BoundedL d where
- class PushR d => BoundedR d where
Highly parameterized Deque type(s)
type family Deque lThreaded rThreaded lDbl rDbl bnd safe elt Source
A family of Deques implementations. A concrete Deque implementation is selected based on the (phantom) type parameters, which encode several choices.
For example, a work stealing deque is threadsafe only on one end and supports push/pop on one end (and popo-only) on the other:
> (Deque NT T D S Grow elt)
Note, however, that the above example is overconstraining in many situations. It demands an implementation which is NOT threadsafe on one end and does NOT support push on one end, whereas both these features would not hurt, if present.
Thus when accepting a queue as input to a function you probably never want to overconstrain by demanding a less-featureful option.
For example, rather than (Deque NT D T S Grow elt)
You would probably want: (Deque nt D T s Grow elt)
The choices that select a queue-variant.
Choice #1 -- thread saftety.
data Threadsafe Source
Haskell IO threads (Control.Concurrent) may concurrently access this end of the queue. Note that this attribute is set separately for the left and right ends.
data Nonthreadsafe Source
Only one thread at a time may access this end of the queue.
Choice #2 -- double or or single functionality on an end.
This end of the queue provides push-only (left) or pop-only
(right) functionality. Thus a SingleEnd / SingleEnd combination
is what is commonly referred to as a single ended queue, whereas
DoubleEnd / DoubleEnd is
a double ended queue. Heterogenous combinations are sometimes
colloquially referred to as "1.5 ended queues".
Choice #3 -- bounded or growing queues:
Choice #4 -- duplication of elements.
Aliases enabling more concise Deque types:
type NT = NonthreadsafeSource
type T = ThreadsafeSource
Aliases for commonly used Deque configurations:
type Queue a = Deque Nonthreadsafe Nonthreadsafe SingleEnd SingleEnd Grow Safe aSource
A traditional single-threaded, single-ended queue.
type ConcQueue a = Deque Threadsafe Threadsafe SingleEnd SingleEnd Grow Safe aSource
A concurrent queue.
type ConcDeque a = Deque Threadsafe Threadsafe DoubleEnd DoubleEnd Grow Safe aSource
A concurrent deque.
type WSDeque a = Deque Nonthreadsafe Threadsafe DoubleEnd SingleEnd Grow Safe aSource
Work-stealing deques (1.5 ended). Typically the worker pushes and pops its own queue (left) whereas thieves only pop (right).
Classes containing Deque operations
class DequeClass d whereSource
Class encompassing the basic queue operations that hold for all single, 1.5, and double ended modes. We arbitrarily call the ends "left" and "right" and choose the natural operations to be pushing on the left and popping on the right.
Methods
Create a new deque. Most appropriate for unbounded deques. If bounded, the size is unspecified.
nullQ :: d elt -> IO BoolSource
pushL :: d elt -> elt -> IO ()Source
Natural push: push onto the left end of the deque.
tryPopR :: d elt -> IO (Maybe elt)Source
Natural pop: pop from the right end of the deque.
Instances
Auxilary type classes.
In spite of hiding the extra phantom type parameters in the DequeClass, we wish to retain the ability for clients to constrain the set of implementations they work with **statically**.
The "unnatural" double ended cases: pop left, push right.
class DequeClass d => PopL d whereSource
Methods
tryPopL :: d elt -> IO (Maybe elt)Source
PopL is not the native operation for the left end, so it requires
that the left end be a DoubleEnd, but places no other requirements
on the input queue.
Instances
class DequeClass d => PushR d whereSource
Methods
pushR :: d elt -> elt -> IO ()Source
Pushing is not the native operation for the right end, so it requires
that end be a DoubleEnd.
Instances