(std mutable deque)

Reference

Overview

Double-ended mutable queue supporting O(1) amortized push and pop operations at both ends.

(import (std mutable deque))

;; Worklist pattern: workers push items, main loop pops items.
(def work (deque))
(deque-push-back! work 1)
(deque-push-back! work 2)
(deque-push-front! work 0)
(deque-pop-front! work)    ; (Some 0)
(deque-pop-back! work)     ; (Some 2)
(deque->list work)         ; (1)

(Deque a) is a mutable double-ended queue. Operations such as deque-push-back! modify the queue in place and return unit. It is well-suited as a worklist in algorithms where new elements are continuously queued and dequeued without requiring persistent snapshots. If persistent history is required, use List or Vec.

Internal representation. The deque is implemented with two internal singly-linked lists: front (storing items in front-to-back order) and back (storing rear items in reverse order). Pushing at either end prepends to the corresponding list in O(1). Popping removes the head element. When one side is exhausted, half of the other side is transferred and reversed. Rebalancing by half guarantees O(1) amortized bounds across alternating operations at opposite ends. deque-length tracks element count in O(1).

Rebalancing during peek. Calling deque-peek-front! or deque-peek-back! may rebalance elements between the internal lists when one side is empty. Although logical content remains unchanged, internal pointers are updated, hence the ! naming convention.

Traversals. deque->list, deque-fold, deque-for-each, and displayed traverse the elements from front to back without altering internal storage.

Empty queue behavior. Popping or peeking from an empty deque returns None without raising exceptions.

Equality and hashing. Two deques are = if they contain equal elements in identical logical order. Because deques are mutable, eq-hash raises an exception to prevent using deques as hash table keys.

Thread safety. Deques are not thread-safe and must not be accessed concurrently without synchronization.

See also: Deque, deque, deque-push-back!, deque-pop-front!

Reference

Types

Functions

Types

Deque

record ↑ Types

Mutable double-ended queue holding elements of type %a.

%a
The element type.

Opaque record type. Access and modify deques through the functions in this module.

See also: deque, list->deque

Functions

deque

function ↑ Functions

(: deque (-> (Deque %a)))
(deque)

Creates an empty mutable deque.

returns
A new deque containing no elements.

See also: list->deque

deque-length

function ↑ Functions

(: deque-length (-> (Deque %a) int))
(deque-length d)

Returns the number of elements in the deque in O(1) time.

d
The deque.
returns
The element count.

See also: deque-empty?

deque-empty?

function ↑ Functions

(: deque-empty? (-> (Deque %a) bool))
(deque-empty? d)

Tests if the deque contains no elements.

d
The deque.
returns
#t if empty, otherwise #f.

See also: deque-length

deque-clear!

function ↑ Functions

(: deque-clear! (-> (Deque %a) void))
(deque-clear! d)

Removes all elements from the deque.

d
The deque to clear.

deque-push-front!

function ↑ Functions

(: deque-push-front! (-> (Deque %a) %a void))
(deque-push-front! d x)

Prepends an element to the front of the deque.

d
The deque to modify.
x
The element to prepend.

See also: deque-push-back!, deque-pop-front!

deque-push-back!

function ↑ Functions

(: deque-push-back! (-> (Deque %a) %a void))
(deque-push-back! d x)

Appends an element to the back of the deque.

d
The deque to modify.
x
The element to append.

See also: deque-push-front!, deque-pop-back!

deque-pop-front!

function ↑ Functions

(: deque-pop-front! (-> (Deque %a) (Option %a)))
(deque-pop-front! d)

Removes and returns the front element, or None if empty.

d
The deque to modify.
returns
(Some x) containing the front element, or None if empty.
(let loop ()
  (match (deque-pop-front! work)
    (None unit)
    ((Some job) (run job) (loop))))

Runs in O(1) amortized time. When the front list is empty, half of the back list is reversed and moved to the front.

See also: deque-pop-back!, deque-peek-front!

deque-pop-back!

function ↑ Functions

(: deque-pop-back! (-> (Deque %a) (Option %a)))
(deque-pop-back! d)

Removes and returns the back element, or None if empty.

d
The deque to modify.
returns
(Some x) containing the back element, or None if empty.

Runs in O(1) amortized time. When the back list is empty, half of the front list is reversed and moved to the back.

See also: deque-pop-front!, deque-peek-back!

deque-peek-front!

function ↑ Functions

(: deque-peek-front! (-> (Deque %a) (Option %a)))
(deque-peek-front! d)

Returns the front element without removing it, or None if empty.

d
The deque. Contents are preserved, but internal storage may be rebalanced.
returns
(Some x) containing the front element, or None if empty.

When the front list is empty, half of the back list is transferred to the front as in deque-pop-front!. Because internal references are modified, the function is named with a trailing !.

See also: deque-pop-front!, deque-peek-back!

deque-peek-back!

function ↑ Functions

(: deque-peek-back! (-> (Deque %a) (Option %a)))
(deque-peek-back! d)

Returns the back element without removing it, or None if empty.

d
The deque. Contents are preserved, but internal storage may be rebalanced.
returns
(Some x) containing the back element, or None if empty.

When the back list is empty, half of the front list is transferred to the back as in deque-pop-back!.

See also: deque-pop-back!, deque-peek-front!

list->deque

function ↑ Functions

(: list->deque (-> (List %a) (Deque %a)))
(list->deque xs)

Constructs a new deque from a list in front-to-back order.

xs
Source list. The head becomes the front of the deque.
returns
A new mutable deque.

The list is adopted as the front list directly without copying, since Bjolang lists are immutable. Counting elements runs in O(n) time.

See also: deque->list, deque

deque->list

function ↑ Functions

(: deque->list (-> (Deque %a) (List %a)))
(deque->list d)

Converts the deque to a list from front to back.

d
The source deque.
returns
A new list containing the deque elements in logical order.

See also: list->deque, deque-fold

deque-fold

function ↑ Functions

(: deque-fold (-> (-?-> %a %b %b) %b (Deque %a) %b))
(deque-fold f init d)

Folds over the elements of the deque from front to back.

f
Accumulator function taking (element, acc) and returning the next accumulator value.
init
Initial accumulator value.
d
The deque to fold.
returns
The final accumulated result.
(deque-fold (fun (x sum) (+ x sum)) 0 (list->deque (list 1 2 3)))   ; 6

Do not mutate the deque inside callback f.

See also: deque-for-each, deque->list

deque-for-each

function ↑ Functions

(: deque-for-each (-> (-?-> %a void) (Deque %a) void))
(deque-for-each f d)

Applies a function to each element from front to back.

f
Function to call on each element.
d
The deque to iterate over.

Traverses the front list followed by the back list. Do not mutate the deque inside callback f.

See also: deque-fold

deque->str

function ↑ Functions

(: deque->str (-> (Deque %a) string))
(deque->str d)

Deprecated: use displayed. Formats the deque as text in the form #<a b c>.

d
The deque to format.
returns
Formatted string representation using displayed for each element.
(displayed (list->deque (list 1 2 3)))   ; "#<1 2 3>"

The same text as displayed gives for a deque. written writes each element as it is written.