abstract-deque-0.3: Abstract, parameterized interface to mutable Deques.

Safe Haskell | Safe-Inferred
Language | Haskell98

Data.Concurrent.Deque.Class

Contents

- Highly parameterized Deque type(s)
  - The choices that select a queue-variant.
    - Choice #1 -- thread safety.
    - Choice #2 -- double or single functionality on an end.
    - Choice #3 -- bounded or growing queues:
    - Choice #4 -- duplication of elements.
  - Aliases enabling more concise Deque types:
  - Aliases for commonly used Deque configurations:
- Class for basic Queue operations
- Extra capabilities: type classes
  - The "unnatural" double ended cases: pop left, push right.
  - Operations that only make sense for bounded queues.

Description

An abstract, parameterizable interface for queues.

This interface includes a non-associated type family for Deques plus separate type classes encapsulating the Deque operations. That is, we separate type selection (type family) from function overloading (vanilla type classes).

This design strives to hide the extra phantom-type parameters from the Class constraints and therefore from the type signatures of client code.

Synopsis

- 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 :: Type -> Type) where
  - newQ :: IO (d elt)
  - nullQ :: d elt -> IO Bool
  - pushL :: d elt -> elt -> IO ()
  - tryPopR :: d elt -> IO (Maybe elt)
  - leftThreadSafe :: d elt -> Bool
  - rightThreadSafe :: d elt -> Bool
- class DequeClass d => PopL (d :: Type -> Type) where
  - tryPopL :: d elt -> IO (Maybe elt)
- class DequeClass d => PushR (d :: Type -> Type) where
  - pushR :: d elt -> elt -> IO ()
- class DequeClass d => BoundedL (d :: Type -> Type) where
  - newBoundedQ :: Int -> IO (d elt)
  - tryPushL :: d elt -> elt -> IO Bool
- class PushR d => BoundedR (d :: Type -> Type) where
  - tryPushR :: d elt -> elt -> IO Bool

# 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 pop-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)`

#### Instances

Instances details

type Deque lt rt l r bnd safe elt Source # | The reference implementation is a fully general Deque. It can thus cover the full configuration space.
Instance details Defined in Data.Concurrent.Deque.Reference.DequeInstance type Deque lt rt l r bnd safe elt = SimpleDeque elt

## The choices that select a queue-variant.

### Choice #1 -- thread safety.

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 single functionality on an end.

data SingleEnd Source #

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. Heterogeneous combinations are sometimes colloquially referred to as "1.5 ended queues".

data DoubleEnd Source #

This end of the queue supports both push and pop.

### Choice #3 -- bounded or growing queues:

data Bound Source #

The queue has bounded capacity.

data Grow Source #

The queue can grow as elements are added.

### Choice #4 -- duplication of elements.

data Safe Source #

The queue will not duplicate elements.

data Dup Source #

Pop operations may possibly duplicate elements. Hopefully with low probability!

## Aliases enabling more concise Deque types:

type S = SingleEnd Source #

type D = DoubleEnd Source #

type NT = Nonthreadsafe Source #

type T = Threadsafe Source #

## Aliases for commonly used Deque configurations:

type Queue a = Deque Nonthreadsafe Nonthreadsafe SingleEnd SingleEnd Grow Safe a Source #

A traditional single-threaded, single-ended queue.

type ConcQueue a = Deque Threadsafe Threadsafe SingleEnd SingleEnd Grow Safe a Source #

A concurrent queue.

type ConcDeque a = Deque Threadsafe Threadsafe DoubleEnd DoubleEnd Grow Safe a Source #

A concurrent deque.

type WSDeque a = Deque Nonthreadsafe Threadsafe DoubleEnd SingleEnd Grow Safe a Source #

Work-stealing deques (1.5 ended). Typically the worker pushes and pops its own queue (left) whereas thieves only pop (right).

# Class for basic Queue operations

class DequeClass (d :: Type -> Type) where Source #

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

newQ :: IO (d elt) Source #

Create a new deque. Most appropriate for unbounded deques. If bounded, the size is unspecified.

nullQ :: d elt -> IO Bool Source #

Is the queue currently empty? Beware that this can be a highly transient state.

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.

leftThreadSafe :: d elt -> Bool Source #

Runtime indication of thread saftey for `pushL` (and `popL`). (Argument unused.)

rightThreadSafe :: d elt -> Bool Source #

Runtime indication of thread saftey for `tryPopR` (and `pushR`). (Argument unused.)

#### Instances

Instances details

DequeClass SimpleDeque Source # |
Instance details Defined in Data.Concurrent.Deque.Reference Methods newQ :: IO (SimpleDeque elt) Source # nullQ :: SimpleDeque elt -> IO Bool Source # pushL :: SimpleDeque elt -> elt -> IO () Source # tryPopR :: SimpleDeque elt -> IO (Maybe elt) Source # leftThreadSafe :: SimpleDeque elt -> Bool Source # rightThreadSafe :: SimpleDeque elt -> Bool Source #
DequeClass d => DequeClass (DebugDeque d) Source # |
Instance details Defined in Data.Concurrent.Deque.Debugger Methods newQ :: IO (DebugDeque d elt) Source # nullQ :: DebugDeque d elt -> IO Bool Source # pushL :: DebugDeque d elt -> elt -> IO () Source # tryPopR :: DebugDeque d elt -> IO (Maybe elt) Source # leftThreadSafe :: DebugDeque d elt -> Bool Source # rightThreadSafe :: DebugDeque d elt -> Bool Source #

# Extra capabilities: type classes

These classes provide a more programmer-friendly constraints than directly using the phantom type parameters to constrain queues in user code. Also note that instances can be provided for types outside the type `Deque` type family.

We still make a distinction between the different capabilities (e.g. single-ended / double ended), and thus we need the below type classes for the additional operations unsupported by the minimal DequeClass.

## The "unnatural" double ended cases: pop left, push right.

class DequeClass d => PopL (d :: Type -> Type) where Source #

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

Instances details

PopL SimpleDeque Source # |
Instance details Defined in Data.Concurrent.Deque.Reference Methods tryPopL :: SimpleDeque elt -> IO (Maybe elt) Source #
PopL d => PopL (DebugDeque d) Source # |
Instance details Defined in Data.Concurrent.Deque.Debugger Methods tryPopL :: DebugDeque d elt -> IO (Maybe elt) Source #

class DequeClass d => PushR (d :: Type -> Type) where Source #

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

Instances details

PushR SimpleDeque Source # |
Instance details Defined in Data.Concurrent.Deque.Reference Methods pushR :: SimpleDeque elt -> elt -> IO () Source #

## Operations that only make sense for bounded queues.

class DequeClass d => BoundedL (d :: Type -> Type) where Source #

Methods

newBoundedQ :: Int -> IO (d elt) Source #

Create a new, bounded deque with a specified capacity.

tryPushL :: d elt -> elt -> IO Bool Source #

For a bounded deque, pushing may fail if the deque is full.

#### Instances

Instances details

BoundedL SimpleDeque Source # |
Instance details Defined in Data.Concurrent.Deque.Reference Methods newBoundedQ :: Int -> IO (SimpleDeque elt) Source # tryPushL :: SimpleDeque elt -> elt -> IO Bool Source #

class PushR d => BoundedR (d :: Type -> Type) where Source #

Methods

tryPushR :: d elt -> elt -> IO Bool Source #

For a bounded deque, pushing may fail if the deque is full.

#### Instances

Instances details

BoundedR SimpleDeque Source # |
Instance details Defined in Data.Concurrent.Deque.Reference Methods tryPushR :: SimpleDeque elt -> elt -> IO Bool Source #