Data.Queue
module Data
A first-in-first-out queue.
Opt-in: nothing here is in scope until using Data.Queue.
using Data.QueueA banker's queue: front holds the elements ready to leave, back holds what was most recently added, reversed. enqueue conses onto back; dequeue takes front's head, and only rotates back (reversing it into front) when front runs out. Both operations are amortized O(1), versus the O(n) enqueue a single-list queue would pay for.
let q = Queue.from([1, 2, 3])
q.enqueue(4).items # => [1, 2, 3, 4]
q.dequeue # => Just((1, Queue(2, 3)))
q.peek # => Just(1)items is +@front + @back.reverse+, so the queue is not opaque: it is always a real list you can hand to anything, the same promise Data.Set makes.
Unlike a set, a queue's representation is NOT canonical: Queue.from([1,2]) and Queue.from([1]).enqueue(2) hold the same elements in different front/back splits, so they are structurally unequal even though they answer the same to every method. == is therefore overloaded to compare items rather than the record fields directly, but that overload only reaches ordinary == calls. Two such queues used as map keys, or matched against each other as record patterns, still compare structurally on both backends, and can disagree with ==.
Every method answers with a new queue rather than changing the receiver. enqueue! and dequeue! come free from the ! rebinding form.
record Queue<A>
A queue of elements, split into a ready-to-leave front and a most-recently-added, reversed back.
Build one with Queue.from rather than by hand.
Fields
front[A]optionalback[A]optional
Implements Enumerable, Foldable, Monoid, Showable, Blankable.
Methods
reduce Enumerable Foldable
reduce(acc: B, f: (B -> A -> B)) -> BFolds from front to back.
This is Queue's Enumerable/Foldable primitive.
Parameters
acc- the initial accumulator
f- combines the accumulator with each element
Returns the final accumulator
Examples
Queue.from([1, 2, 3]).reduce(0) { |sum, x| sum + x } # => 6combine Monoid
combine(other: Queue<A>) -> Queue<A>Combines two queues, this one's elements followed by the argument's.
Parameters
other- the queue to append
Returns this queue's elements, then other's
Examples
Queue.from([1, 2]).combine(Queue.from([3, 4])).items # => [1, 2, 3, 4]items
items : [A]Returns the elements front to back. Never opaque: this is a real list.
Returns the elements, front first
Examples
Queue.from([1, 2]).enqueue(3).items # => [1, 2, 3]enqueue
enqueue(value: A) -> Queue<A>Returns a new queue with value added at the back.
Use enqueue! to rebind the receiver variable.
Parameters
value- the element to add
Returns a queue with value at the back
Examples
Queue.from([1, 2]).enqueue(3).items # => [1, 2, 3]dequeue
dequeue : (A, Queue<A>)?Returns the front element and the queue without it, wrapped in Just, or None for an empty queue.
Rotates back into front (reversing it) when front has run out: the one case that is not O(1), and only amortized so because each element is reversed at most once over the queue's lifetime.
Use dequeue! to rebind the receiver variable.
Returns the front element and the rest, or None
Examples
Queue.from([1, 2, 3]).dequeue # => Just((1, Queue(2, 3)))
Queue.empty.dequeue # => Nonepeek
peek : A?Returns the front element wrapped in Just, or None for an empty queue.
Returns the front element, or None
Examples
Queue.from([1, 2]).peek # => Just(1)
Queue.empty.peek # => Nonecount Foldable
count : IntegerReturns the number of elements.
Returns the number of elements
Examples
Queue.from([1, 2, 3]).count # => 3empty?
empty? : BoolReturns true when the queue has no elements.
Returns true for the empty queue
Examples
Queue.empty.empty? # => true
Queue.from([1]).empty? # => false==
==(other: Queue<A>) -> BoolCompares two queues by their elements, front to back: NOT by their front/back split, which is not canonical. See the file header.
Parameters
other- the queue to compare against
Returns true when both hold the same elements in the same order
Examples
Queue.from([1, 2]) == Queue.from([1]).enqueue(2) # => true+
+(other: Queue<A>) -> Queue<A>
+(other: [A]) -> Queue<A>Appends another queue's elements, or a plain list's.
Parameters
other- the elements to append
Returns this queue's elements, then other's
Examples
Queue.from([1, 2]) + [3, 4] # => Queue(1, 2, 3, 4)
Queue.from([1, 2]) + Queue.from([3]) # => Queue(1, 2, 3)From Enumerable
map- Applies
fto each item and collects the results into a list. mapIndexed- Applies
fto each item and its 0-based position, and collects the results into a list. filter- Returns the items for which
predanswerstrue. flatMap- Applies
fto each item, expecting a list back, and concatenates the results into one flat list. collect- Applies
fto each item, expecting anOptionalback, and returns the values that were present: unwrapped.
From Foldable
each- Calls
fwith each item, for its side effects. eachIndexed- Calls
fwith each item and its 0-based position, for its side effects. all?- Returns
truewhen every item satisfiespred. any?- Returns
truewhen at least one item satisfiespred. find- Returns the first item satisfying
pred, orNonewhen nothing does.
From Monoid
repeat- Combines this value with itself
ntimes.
From Showable
module Data.Queue
Constructors for Queue.