Standard library · Collections

coll/deque

Imported as import "coll/deque" as deque, its names are then deque.…. Every signature below is the one the checker infers.

A queue with both ends open: push and pop at the front or the back, each in constant time on average. A deque is a value — every operation gives a new one and leaves the old as it was — so it is the queue to keep in a loop's state or a strand's, where a list would cost a walk to reach its far end.

Two lists, one for each end, the front's in order and the back's reversed; when one runs dry the other is turned round to feed it, which is the walk a plain list would make on every pop, made once in a while.

q = deque.push_back(deque.push_back(deque.new(), "first"), "second")
deque.pop_front(q) |> opt_map(\p -> fst(p))   # => Some(first)
deque.items(q)                                # => Cons(first, Cons(second, Nil))
deque.size(q)                                 # => 2

Types

Deque(a)

• Deque(front: List(a), back: List(a), size: Int)

Functions

fn new() -> Deque('a)

deque.is_empty(deque.new())   # => true

fn of(items: List('a)) -> Deque('a)

deque.items(deque.of(Cons(1, Cons(2, Nil))))   # => Cons(1, Cons(2, Nil))

fn size(q: Deque('a)) -> Int

deque.size(deque.of(Cons(1, Cons(2, Cons(3, Nil)))))   # => 3

fn is_empty(q: Deque('a)) -> Bool

deque.is_empty(deque.of(Cons(1, Nil)))   # => false

fn push_front(q: Deque('a), x: 'a) -> Deque('a)

deque.items(deque.push_front(deque.of(Cons(2, Nil)), 1))   # => Cons(1, Cons(2, Nil))

fn push_back(q: Deque('a), x: 'a) -> Deque('a)

deque.items(deque.push_back(deque.of(Cons(1, Nil)), 2))   # => Cons(1, Cons(2, Nil))

fn pop_front(q: Deque('a)) -> Option(('a, Deque('a)))

The front element and the deque without it, or None when it is empty.

q = deque.of(Cons(1, Cons(2, Nil)))
deque.pop_front(q) |> opt_map(\p -> fst(p))                   # => Some(1)
deque.pop_front(q) |> opt_map(\p -> deque.items(snd(p)))     # => Some(Cons(2, Nil))
deque.pop_front(deque.new())                                  # => None

fn pop_back(q: Deque('a)) -> Option(('a, Deque('a)))

q = deque.of(Cons(1, Cons(2, Nil)))
deque.pop_back(q) |> opt_map(\p -> fst(p))   # => Some(2)

fn peek_front(q: Deque('a)) -> Option('a)

deque.peek_front(deque.of(Cons(1, Cons(2, Nil))))   # => Some(1)

fn peek_back(q: Deque('a)) -> Option('a)

deque.peek_back(deque.of(Cons(1, Cons(2, Nil))))   # => Some(2)

fn items(q: Deque('a)) -> List('a)

Everything, front to back.

q = deque.push_front(deque.push_back(deque.new(), 2), 1)
deque.items(q)   # => Cons(1, Cons(2, Nil))

Tests

• test_a_queue
• test_both_ends
• test_drains_in_order