Nanyx
PlaygroundPackages

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.