Deque

Deque: functional double-ended queue with O(1) size tracking.

Representation: Deque(size, front, back) front is in natural order (head = front of deque) back is in reverse order (head = back of deque)

Complexity: push_front / push_back O(1) worst case pop_front / pop_back O(1) amortised (O(n) worst case on rebalance) peek_front / peek_back O(1) amortised size O(1) concat O(|d2|) amortised to_list / from_list O(n)

Types

ptypeDequeDeque(a) = Deque(Int, List(a), List(a))#

Functions

fnallall(d : Deque(a), f : a -> Bool) : Bool#

True when f returns true for all elements (vacuously true for empty).

fnanyany(d : Deque(a), f : a -> Bool) : Bool#

True when f returns true for at least one element.

fnconcatconcat(d1 : Deque(a), d2 : Deque(a)) : Deque(a)#

Append all elements of d2 after d1. O(|d2|) amortised.

fnemptyempty() : Deque(a)#

An empty deque.

fnfilterfilter(d : Deque(a), pred : a -> Bool) : Deque(a)#

Keep only elements satisfying pred. O(n).

fnfold_leftfold_left(d : Deque(a), acc : b, f) : b#

Left fold over elements from front to back. O(n).

fnfold_rightfold_right(d : Deque(a), acc : b, f) : b#

Right fold over elements from back to front. O(n).

fnfrom_listfrom_list(xs : List(a)) : Deque(a)#

Build a deque from a list. First element becomes the front. O(n).

fnis_emptyis_empty(d : Deque(a)) : Bool#

True when the deque contains no elements.

fnmapmap(d : Deque(a), f : a -> b) : Deque(b)#

Apply f to every element, returning a new deque in the same order. O(n).

fnpeek_backpeek_back(d : Deque(a)) : Option(a)#

Return Some(back element) without removing, or None if empty. O(1) amortised.

fnpeek_frontpeek_front(d : Deque(a)) : Option(a)#

Return Some(front element) without removing, or None if empty. O(1) amortised.

fnpop_backpop_back(d : Deque(a)) : (Deque(a), Option(a))#

Remove the back element. Returns (rest, Some(elem)) or (empty, None). O(1) amortised.

fnpop_frontpop_front(d : Deque(a)) : (Option(a), Deque(a))#

Remove the front element. Returns (Some(elem), rest) or (None, empty). O(1) amortised.

fnpush_backpush_back(d : Deque(a), x : a) : Deque(a)#

Add an element to the back of the deque. O(1).

fnpush_frontpush_front(d : Deque(a), x : a) : Deque(a)#

Add an element to the front of the deque. O(1).

fnsingletonsingleton(x : a) : Deque(a)#

A deque containing exactly one element.

fnsizesize(d : Deque(a)) : Int#

Number of elements. O(1).

fnto_listto_list(d : Deque(a)) : List(a)#

Elements from front to back as a list. O(n).