Is there a purely functional implementation for a limited queue with peek () in O (1)?

Question

I want to maintain an immutable, limited FIFO queue from which I can delete the oldest values ​​after a certain time. In Scala, an immutable .Queue works well for size-limited queues (.size seems to be O (N) since it is internally based on List, but I can maintain the size separately), but there seems to be no cheap way to access the head element so that checking the age of the oldest value for something cheaper than O (N), so I can not check the expiration status of the oldest record. Any pointers to a purely functional (immutable) implementation?

Answer 1

In this article, Haskell: queues without pointers , describes a purely functional queue with an amortized cost of O (1) (edit: to add and remove items). I think the data structure comes from Chris Okasaki, and more details in his book .

The basic idea is to split the queue into two lists, one for the front and one for the back. New items are added to the "front". The back is stored in reverse order to facilitate pushing out items. When all the "back" elements are gone, the "front" flips over and is again identified as "back". This data structure has an amortized cost of O (1) for these operations, but, obviously, with some work it can be reduced to O (1), in fact.

Edit : The Okasaki article describes an elegant, purely functional implementation of queues and deques. Deques allows you to add or remove items from either end. All such operations are O (1), the worst case.

Answer 2

The immutable.Queue standard in Scala can be adapted to work this way for amortized complexity. Note, however, that the peek operation will return a new queue, or, in the opposite case, consecutive calls to peek could very well be made in O (n).

You can either extend Queue or create a new class that adapts it. Here is the version expanding it:

 import scala.collection._ import generic._ import immutable.Queue import mutable.{ Builder, ListBuffer } class MyQueue[+A] protected(in0: List[A], out0: List[A]) extends scala.collection.immutable.Queue[A](in0, out0) with GenericTraversableTemplate[A, MyQueue] with LinearSeqLike[A, MyQueue[A]] { override def companion: GenericCompanion[MyQueue] = MyQueue def peek: (A, MyQueue[A]) = out match { case Nil if !in.isEmpty => val rev = in.reverse ; (rev.head, new MyQueue(Nil, rev)) case x :: xs => (x, this) case _ => throw new NoSuchElementException("dequeue on empty queue") } override def tail: MyQueue[A] = if (out.nonEmpty) new MyQueue(in, out.tail) else if (in.nonEmpty) new MyQueue(Nil, in.reverse.tail) else throw new NoSuchElementException("tail on empty queue") override def enqueue[B >: A](elem: B) = new MyQueue(elem :: in, out) // This ought to be override, but scalac doesn't think so! def enqueue[B >: A](iter: Iterable[B]) = new MyQueue(iter.toList.reverse ::: in, out) override def dequeue: (A, MyQueue[A]) = out match { case Nil if !in.isEmpty => val rev = in.reverse ; (rev.head, new MyQueue(Nil, rev.tail)) case x :: xs => (x, new MyQueue(in, xs)) case _ => throw new NoSuchElementException("dequeue on empty queue") } override def toString() = mkString("MyQueue(", ", ", ")") } object MyQueue extends SeqFactory[MyQueue] { implicit def canBuildFrom[A]: CanBuildFrom[Coll, A, MyQueue[A]] = new GenericCanBuildFrom[A] def newBuilder[A]: Builder[A, MyQueue[A]] = new ListBuffer[A] mapResult (x => new MyQueue[A](Nil, x.toList)) override def empty[A]: MyQueue[A] = EmptyQueue.asInstanceOf[MyQueue[A]] override def apply[A](xs: A*): MyQueue[A] = new MyQueue[A](Nil, xs.toList) private object EmptyQueue extends MyQueue[Nothing](Nil, Nil) { } } 

Answer 3

If I understand the question correctly, you are looking for a double queue (deque). There are documents of Okasaki, Kaplan and Tarjan on purely functional images. As for the implementations, the simplest is that I intend to use the standard implementation of collection.immutable.IndexedSeq , which is collection.immutable.Vector , according to this table , the fixed costs for head and last estimated (he says tail , but I would assume that last also O (1)).

Okasaki / Kaplan / Tarjan seems to be implemented by Henry Ware .

Another implementation that comes to mind is Hintze's FingerTree, for which there are various implementations in scala. Scalaz has one that I put in a separate package some time ago, since I use it a lot. According to a presentation by Daniel Spivak (I don’t remember where I saw it), FingerTree is rather slow, albeit in constant time factors - as well as the Henry Weir page says it is slower than its other implementation.

Answer 4

If you are looking for a two-way queue (deque), Scala 1.13 (June 2019, eight years later) now has ArrayDeque

An implementation of a two-way queue that internally uses a resizable circular buffer.

Append, prepend, removeFirst, removeLast and random access (indexed-lookup and indexed-replace) occupy an amortized constant time.

As a rule, deletions and insertions with the index i -th are equal to O(min(i, ni)) and, therefore, insertions and deletions from the end / beginning are quick.

This comes from scala/collection-strawman PR 490 , combined with Scala in the c0129af commit .