queue
Immutable queues, first in, first out
Import it as nanyx/queue. A Queue takes values in at the back with enqueue and gives them out at the front with dequeue, each in constant time averaged over all the calls, and each gives back a new queue, leaving the one it was given as it was.
import nanyx/queue
def waiting = Queue["ada", "bob"] \enqueue("cy")
match Queue.dequeue(waiting)
| #some(next, rest) -> println("{next} {Queue.toList(rest)}") -- ada [bob, cy]
| #none -> println("nobody")
Reference
Immutable queues: first in, first out.
A Queue(a) takes values in at the back with Queue.enqueue and gives them out at the front
with Queue.dequeue. It holds two lists, the front in order and the back reversed: enqueue
puts a value on the back list, and dequeue takes one off the front list, reversing the back list
into it when it runs out. Each value is moved once, so both take constant time averaged over all
the calls. Nothing about a queue changes once it is made: each gives back a new queue, and the old
one still holds what it held.
Two queues are == when they hold equal values in the same order, however each splits them
between its two lists, and Queue.hash agrees. Queue.toString writes one as
Queue[1, 2, 3], the front first.
Each function is attached to Queue, so with import nanyx/queue it is called as
Queue.enqueue(q, 5), or as q \enqueue(5). A literal makes one, the first value at the front:
Queue[1, 2, 3], or [1, 2, 3] where a queue is expected.
Queue
type Queue(a) = protected (front: list(a), back: list(a), length: int)
Queue.empty
def Queue.empty: Queue(a)
The queue with nothing in it.
Queue.fromList
def Queue.fromList: list(a) -> Queue(a)
A queue holding xs, the first of them at the front.
Queue.fromArray
def Queue.fromArray: array(a) -> Queue(a)
A queue holding xs, the first of them at the front. What a literal builds a queue with,
Queue[1, 2, 3], or [1, 2, 3] where a queue is expected.
Queue.fromSeq
def Queue.fromSeq: [c] ([c] seq(a)) -> Queue(a)
A queue holding the elements of s, pulled now, the first of them at the front. It requires the
contexts the sequence’s steps do.
Queue.build
def Queue.build: [c, d] ([c] () -> [d] seq(a)) -> Queue(a)
A queue of what block yields, the first at the front. The same as
seq(block) \Queue.fromSeq.
Queue.enqueue
def Queue.enqueue: Queue(a), a -> Queue(a)
queue with value at the back of it.
Queue.dequeue
def Queue.dequeue: Queue(a) -> #some(a, Queue(a)) | #none
The value at the front of queue and the queue behind it, or #none when it is empty.
Queue.peek
def Queue.peek: Queue(a) -> #some(a) | #none
The value at the front of queue, or #none when it is empty.
Queue.isEmpty
def Queue.isEmpty: Queue(a) -> bool
Whether queue has nothing in it.
Queue.length
def Queue.length: Queue(a) -> int
How many values are in queue.
Queue.toSeq
def Queue.toSeq: Queue(a) -> seq(a)
The values in queue, the front one first, as a sequence. A queue is Iterable by it, so a
for loop walks one.
Queue.toList
def Queue.toList: Queue(a) -> list(a)
The values in queue, the front one first.
Queue.reduce
def Queue.reduce: [c] Queue(a), ([c] (a, a) -> a) -> #some(a) | #none
The elements of q, from the front, combined with f, in order, starting from the first: a
queue of 1 to 5 reduced with { * } is #some(120), and an empty one, having no first
element, gives #none. To start from another value, use list.fold.
Queue.`==`
def Queue.`==`: [Eq(a)] Queue(a), Queue(a) -> bool
Whether p and q hold equal values in the same order.
Queue.hash
def Queue.hash: [Hash(a)] Queue(a) -> int
The hash of the values in queue, in order: the same for any two queues == finds equal.
Queue.toString
def Queue.toString: [ToString(a)] Queue(a) -> string
queue as its literal is written, the front first: Queue[1, 2, 3], and Queue[] when it is
empty.