Queue

A Queue is like a List but with a reduced interface. Items can only be accessed at the start of the Queue, and only added at the end. Construct a Queue either by calling fromList or by creating an empty Queue and enque elements at the end. Access the first element using deque. Example:

Jobs : Queue PrintJob

addPrintJob: Queue -> Queue,
addPrintJob = \queue ->
    queue |> Queue.enque

nextPrintJob: Queue -> Result {remaining: Queue PrintJob, job: PrintJob} NoJobsAvailable
nextPrintJob = \jobQueue ->
    when jobQueue |> Queue.deque is
        Err QueueWasEmpty -> Err NoJobsAvailable
        Ok {queue, elem} -> Ok {remaining: queue, job: elem }

Queue a

empty : {} -> Queue *

Create an empty Queue.

emptyQueue = Queue.empty {}

enque : Queue a, a -> Queue a

Add ("enque") an element at the end of the queue.

Queue.empty {} |> Queue.enque "a" |> Queue.enque "b"== Queue.fromList ["a", "b"]

deque : Queue a -> Result { queue : Queue a, elem : a } [QueueWasEmpty]

Deque the first element in the queue. Returns the remaining queue and the retreived element if succesful, and Err QueueWasEmpty if the queue was empty.

expect Queue.empty {} |> Queue.deque == Err QueueWasEmpty
expect
    Queue.empty {} |> Queue.enque "a" |> Queue.enque "b" |> Queue.deque
    == Ok {queue: Queue.empty {} |> Queue.enque "b", elem: "a"}

fromList : List a -> Queue a

Create a Queue from a List. The first element of the list will be the first element of the queue.

expect Queue.fromList [] == Queue.empty {}
expect Queue.fromList ["a","b"] == Queue.empty {} |> Queue.enque "a" |> Queue.enque "b"

size : Queue * -> Nat

Determine the number of items in the queue.

expect Queue.empty {} |> Queue.size == 0
expect Queue.empty {} |> Queue.enque "a" |> Queue.enque "b" |> Queue.size == 2

peek : Queue a -> Result a [QueueWasEmpty]

Peek at the first item in the queue.

expect Queue.empty {} |> Queue.peek == Err QueueWasEmpty
expect
     Queue.empty {}
        |> Queue.enque 1
        |> Queue.enque 2
        |> Queue.peek
        == Ok 1

isEmpty : Queue * -> Bool

Determine if the queue is empty.

expect Queue.empty {} |> Queue.isEmpty
expect Queue.empty {} |> Queue.enque 1 |> Queue.isEmpty |> Bool.not

inFrontOf : Queue a, Queue a -> Queue a

Place the first queue in front of the second queue.

expect
    queue1 = Queue.empty {} |> Queue.enque 1 |> Queue.enque 2
    queue2 = Queue.empty {} |> Queue.enque 3 |> Queue.enque 4
    queue1
        |> Queue.inFrontOf queue2
        == Queue.fromList [1, 2, 3 ,4]

process : Queue a, state, (state, a -> state) -> state

Process the queue, performing an action and accumulating a state. Analogous to walking a List.

expect Queue.empty {} |> Queue.process 0 Num.add == 0
expect
    Queue.empty {} |> Queue.enque "a" |> Queue.enque "b" |> Queue.enque "c"
    |> Queue.process "" Str.concat
    == "abc"