~/bend-docscommunity

lib.bend checks

raw source on the hub · import 0x61995e10548d45d2441f35cc3adcea7b/lib.bend as Lib

Queue — foundational two-list FIFO for Bend. Publish entry for this package. Depends only on Base (does not reimplement List).

Encoding: front + rear (rear stored reversed). Amortized O(1) enqueue/dequeue via Queue.norm (rotate rear→front when front is empty). Quantity: Queue<a, A> is Kind(a), same convention as List/Maybe.

1 import
import Base

Types

type Queue source · line 9 · raw

@-a:Quant -> @-A:Kind(a) -> Kind(a)

type Queue.Deq source · line 13 · raw

@-a:Quant -> @-A:Kind(a) -> Kind(a)

Dequeue view: head + rest queue (Kind-friendly; A & Queue is Type, not Kind(a)).

Definitions

def Queue.empty source · line 16 · raw

@-a:Quant -> @-A:Kind(a) -> Queue<a, A>

def Queue.enqueue source · line 19 · raw

@-a:Quant -> @-A:Kind(a) -> @q:Queue<a, A> -> @x:A -> Queue<a, A>

def Queue.norm source · line 25 · raw

@-a:Quant -> @-A:Kind(a) -> @q:Queue<a, A> -> Queue<a, A>

When front is empty, reverse rear into front (and clear rear).

def Queue.dequeue.go source · line 34 · raw

@-a:Quant -> @-A:Kind(a) -> @q:Queue<a, A> -> Maybe<a, Queue.Deq<a, A>>

def Queue.dequeue source · line 43 · raw

@-a:Quant -> @-A:Kind(a) -> @q:Queue<a, A> -> Maybe<a, Queue.Deq<a, A>>

def Queue.peek.go source · line 46 · raw

@-a:Quant -> @-A:Kind(a) -> @q:Queue<a, A> -> Maybe<a, A>

def Queue.peek source · line 55 · raw

@-a:Quant -> @-A:Kind(a) -> @q:Queue<a, A> -> Maybe<a, A>

def Queue.is_empty source · line 58 · raw

@-a:Quant -> @-A:Kind(a) -> @q:Queue<a, A> -> Bool

def Queue.length source · line 67 · raw

@-a:Quant -> @-A:Kind(a) -> @q:Queue<a, A> -> Nat

def Queue.to_list source · line 73 · raw

@-a:Quant -> @-A:Kind(a) -> @q:Queue<a, A> -> List<a, A>

FIFO order: front ++ reverse(rear).

def Queue.from_list source · line 78 · raw

@-a:Quant -> @-A:Kind(a) -> @xs:List<a, A> -> Queue<a, A>