Module

Data.CatQueue

This module defines a strict double-ended queue.

The queue implementation is based on a pair of lists where all operations require O(1) amortized time.

However, any single uncons operation may run in O(n) time.

See Simple and Efficient Purely Functional Queues and Dequeues (Okasaki 1995)

#CatQueue 

data CatQueue a

A strict double-ended queue (dequeue) representated using a pair of lists.

Constructors

Instances

#empty 

empty :: forall a. CatQueue a

Create an empty queue.

Running time: O(1)

#null 

null :: forall a. CatQueue a -> Boolean

Test whether a queue is empty.

Running time: O(1)

#singleton 

singleton :: forall a. a -> CatQueue a

Create a queue containing a single element.

Running time: O(1)

#length 

length :: forall a. CatQueue a -> Int

Number of elements in queue.

Running time: O(n) in length of queue.

#cons 

cons :: forall a. a -> CatQueue a -> CatQueue a

Append an element to the beginning of the queue, creating a new queue.

Running time: O(1)

#snoc 

snoc :: forall a. CatQueue a -> a -> CatQueue a

Append an element to the end of the queue, creating a new queue.

Running time: O(1)

#uncons 

uncons :: forall a. CatQueue a -> Maybe (Tuple a (CatQueue a))

Decompose a queue into a Tuple of the first element and the rest of the queue.

Running time: O(1)

Note that any single operation may run in O(n).

#unsnoc 

unsnoc :: forall a. CatQueue a -> Maybe (Tuple a (CatQueue a))

Decompose a queue into a Tuple of the last element and the rest of the queue.

Running time: O(1)

Note that any single operation may run in O(n).

#fromFoldable 

fromFoldable :: forall f a. Foldable f => f a -> CatQueue a

Convert any Foldable into a CatQueue.

Running time: O(n)

Modules