Module

Data.CatQueue

Package
purescript-catenable-lists
Repository
purescript/purescript-catenable-lists

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 Source

data CatQueue a

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

Constructors

Instances

#empty Source

empty :: forall a. CatQueue a

Create an empty queue.

Running time: O(1)

#null Source

null :: forall a. CatQueue a -> Boolean

Test whether a queue is empty.

Running time: O(1)

#singleton Source

singleton :: forall a. a -> CatQueue a

Create a queue containing a single element.

Running time: O(1)

#length Source

length :: forall a. CatQueue a -> Int

Number of elements in queue.

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

#cons Source

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 Source

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 Source

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 Source

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 Source

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

Convert any Foldable into a CatQueue.

Running time: O(n)

Modules
Data.CatList
Data.CatQueue