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

Internal: Deque(size, front, back) — front is in order, back is reversed.

Functions

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

True when f returns true for every element (vacuously true for an empty deque).

Examples

march> Deque.all(Deque.from_list([2, 4]), fn x -> x % 2 == 0)
true
march> Deque.all(Deque.from_list([2, 3]), fn x -> x % 2 == 0)
false
march> Deque.all(Deque.empty(), fn x -> x > 100)
true

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

True when f returns true for at least one element (false for an empty deque).

Examples

march> Deque.any(Deque.from_list([1, 2, 3]), fn x -> x > 2)
true
march> Deque.any(Deque.empty(), fn x -> x > 2)
false

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

Append all elements of d2 after d1. O(|d2|): each element of d2 is pushed onto the back of d1.

Examples

march> Deque.to_list(Deque.concat(Deque.from_list([1, 2]), Deque.from_list([3, 4])))
[1, 2, 3, 4]
march> Deque.to_list(Deque.concat(Deque.empty(), Deque.singleton(1)))
[1]

fnemptyempty() : Deque(a)#

An empty deque.

Examples

march> Deque.to_list(Deque.empty())
[]
march> Deque.size(Deque.empty())
0

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

Keep only the elements satisfying pred, preserving order. O(n). Every element of the result satisfies pred (an abstract refinement p, as for List.filter): Deque.to_list(Deque.filter(d, fn y -> y > 0)) is a List({Int | _ > 0}).

Examples

march> Deque.to_list(Deque.filter(Deque.from_list([1, 2, 3, 4]), fn x -> x % 2 == 0))
[2, 4]
march> Deque.size(Deque.filter(Deque.from_list([1, 3]), fn x -> x > 5))
0

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

Left fold over the elements from front to back; f is called as f(acc, x). O(n).

Examples

march> Deque.fold_left(Deque.from_list([1, 2, 3]), 0, fn (acc, x) -> acc * 10 + x)
123
march> Deque.fold_left(Deque.empty(), 5, fn (acc, x) -> acc + x)
5

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

Right fold: processes elements from back to front; f is called as f(x, acc). O(n).

Examples

march> Deque.fold_right(Deque.from_list([1, 2, 3]), 0, fn (x, acc) -> acc * 10 + x)
321
march> Deque.fold_right(Deque.from_list([1, 2, 3]), [], fn (x, acc) -> Cons(x, acc))
[1, 2, 3]

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

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

Examples

march> Deque.peek_front(Deque.from_list([1, 2, 3]))
Some(1)
march> Deque.size(Deque.from_list([]))
0

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

True when the deque contains no elements. O(1).

Examples

march> Deque.is_empty(Deque.empty())
true
march> Deque.is_empty(Deque.singleton(1))
false

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

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

Examples

march> Deque.to_list(Deque.map(Deque.from_list([1, 2, 3]), fn x -> x * 10))
[10, 20, 30]
march> Deque.to_list(Deque.map(Deque.empty(), fn x -> x + 1))
[]

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

Return Some(back element) without removing it, or None if empty. O(1) amortised (O(n) when the back list is empty and the front list must be reversed; the reversal is not kept).

Examples

march> Deque.peek_back(Deque.from_list([1, 2, 3]))
Some(3)
march> Deque.peek_back(Deque.push_front(Deque.empty(), 5))
Some(5)
march> Deque.peek_back(Deque.empty())
None

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

Return Some(front element) without removing it, or None if empty. O(1) amortised (O(n) when the front list is empty and the back list must be reversed; the reversal is not kept).

Examples

march> Deque.peek_front(Deque.from_list([1, 2, 3]))
Some(1)
march> Deque.peek_front(Deque.push_back(Deque.empty(), 5))
Some(5)
march> Deque.peek_front(Deque.empty())
None

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

Remove the back element. Returns (rest, Some(elem)), or (empty(), None) if the deque is empty. Note the tuple order is the mirror of pop_front. O(1) amortised: when the back list is exhausted the front list is reversed once into the back.

Examples

march> match Deque.pop_back(Deque.from_list([1, 2, 3])) do (rest, x) -> (Deque.to_list(rest), x) end
([1, 2], Some(3))
march> match Deque.pop_back(Deque.empty()) do (rest, x) -> (Deque.size(rest), x) end
(0, None)

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

Remove the front element. Returns (Some(elem), rest), or (None, empty()) if the deque is empty. O(1) amortised: when the front list is exhausted the back list is reversed once into the front.

Examples

march> match Deque.pop_front(Deque.from_list([1, 2, 3])) do (x, rest) -> (x, Deque.to_list(rest)) end
(Some(1), [2, 3])
march> match Deque.pop_front(Deque.empty()) do (x, rest) -> (x, Deque.size(rest)) end
(None, 0)

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

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

Examples

march> Deque.to_list(Deque.push_back(Deque.from_list([1, 2]), 3))
[1, 2, 3]
march> Deque.to_list(Deque.push_back(Deque.empty(), 1))
[1]

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

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

Examples

march> Deque.to_list(Deque.push_front(Deque.from_list([2, 3]), 1))
[1, 2, 3]
march> Deque.to_list(Deque.push_front(Deque.empty(), 1))
[1]

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

A deque containing exactly one element.

Examples

march> Deque.to_list(Deque.singleton(7))
[7]

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

Number of elements. O(1): the size is stored, not counted.

Examples

march> Deque.size(Deque.from_list([1, 2, 3]))
3
march> Deque.size(Deque.empty())
0

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

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

Examples

march> Deque.to_list(Deque.push_front(Deque.push_back(Deque.empty(), 2), 1))
[1, 2]
march> Deque.to_list(Deque.empty())
[]