Module

Data.CatQueue

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

This module defines a strict 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 queue 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)

#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).

Modules
Data.CatList
Data.CatQueue