HORIZON HASKELLDocslts/ghc-9.10.x248f8f02026-10-05Search names, modules, packages, or :: a typeCtrl K

GHC 9.10.3 · lts/ghc-9.10.x · 248f8f0 · 2026-10-05

Moduleabstract-deque-0.3Haskell98

Data.Concurrent.Deque.Class

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.

  • 16 types
  • 5 classes

Highly parameterized Deque type(s)

1 declaration
familytype family Deque lThreaded rThreaded lDbl rDbl bnd safe elt
#

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)

Instances1Deque
  • type Deque lt rt l r bnd safe elt = SimpleDeque eltDefined in abstract-deque-0.3 · Data.Concurrent.Deque.Reference.DequeInstance · orphan

    The reference implementation is a fully general Deque. It can thus cover the full configuration space.

The choices that select a queue-variant.

Choice #1 -- thread safety.

datadata Threadsafe
#

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.

datadata Nonthreadsafe
#

Only one thread at a time may access this end of the queue.

Choice #2 -- double or single functionality on an end.

datadata SingleEnd
#

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

datadata DoubleEnd
#

This end of the queue supports both push and pop.

Choice #3 -- bounded or growing queues:

datadata Bound
#

The queue has bounded capacity.

datadata Grow
#

The queue can grow as elements are added.

Choice #4 -- duplication of elements.

datadata Safe
#

The queue will not duplicate elements.

datadata Dup
#

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

Aliases enabling more concise Deque types:

Aliases for commonly used Deque configurations:

Class for basic Queue operations

1 declaration
classclass DequeClass (d :: Type -> Type) where
#

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)

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

  • nullQ :: d elt -> IO Bool

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

  • pushL :: d elt -> elt -> IO ()

    Natural push: push onto the left end of the deque.

  • tryPopR :: d elt -> IO (Maybe elt)

    Natural pop: pop from the right end of the deque.

  • leftThreadSafe :: d elt -> Bool

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

  • rightThreadSafe :: d elt -> Bool

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

Instances2DequeClass

Extra capabilities: type classes

0 declarations

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.

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

Methods

  • tryPopL :: d elt -> IO (Maybe elt)

    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.

Instances2PopL
  • PopL SimpleDequeDefined in abstract-deque-0.3 · Data.Concurrent.Deque.Reference
  • PopL d => PopL (DebugDeque d)Defined in abstract-deque-0.3 · Data.Concurrent.Deque.Debugger
classclass DequeClass d => PushR (d :: Type -> Type) where
#

Methods

  • pushR :: d elt -> elt -> IO ()

    Pushing is not the native operation for the right end, so it requires that end be a DoubleEnd.

Instances1PushR
  • PushR SimpleDequeDefined in abstract-deque-0.3 · Data.Concurrent.Deque.Reference

Operations that only make sense for bounded queues.