Article: Doubly Linked List and the Scala Cats Effect Dequeue

We discuss the doubly linked list data structure along with the Scala Cats Effect Dequeue because their practical applications are often similar.

Doubly Linked List and the Scala Cats Effect Dequeue

Table of Contents

Overview of Scala and Monads

A monad represents a value in a context that can be manipulated consistently. Monads are integral to safe, purely functional programming and can be used to encapsulate unsafe program behavior.

Monads will undoubtedly come up in conversations involving the Haskell and Scala programming languages. The current discussion focuses on Scala.

Scala is a high-level, statically typed, compiled, and garbage-collected programming language. Unlike Haskell, Scala is not only functional but also object-oriented.

Some of Scala’s advanced features include things like extension methods. Extension methods allow adding methods to a class separately from its definition.

An Introduction to Scala Cats Effect

To better appreciate what is in the Scala Cats and Cats Effect libraries, it may help to review some of the members in the Scala standard library. These are the map, foldLeft, foldRight, iterate, sequence, and methods. My recommendation would be to understand the map function first and then build from there.

The Scala Cats library is an example of a library that provides type class instances for many of the built-in Scala types constructors. For example, the Scala library, Cats Effect, includes the IO monad and the monads Future, Rand, and Option. These monads have unsafe methods that can be used to access the contents of the monad and perform the side effects. This is why this library is called an “effect system.” Its combined features make it a valuable toolkit for creating concurrent applications.

To define a monad in Scala, one must determine the two required natural transformations or their equivalent:

Pure – the natural transformation corresponding to η:IdC→T inherited from the Applicative type class.

Join – the natural transformation µ:T◦T→T.

The below Scala Cats Effect use case is two random number calculations. The two computations, however, will be the same:

package com.uequations

import cats.effect.{IO, IOApp}

import scala.util.Random

object IORandom extends IOApp.Simple {

  val ioByVariable: IO[Unit] = {
    val random = new Random(0L)
    val x: IO[Int] = IO(random.nextInt)
    for {
      a <- x
      b <- x
      _ <- IO(println(("ioByVariable", a, b)))
    } yield (a, b)

  val ioByComposition: IO[Unit] = {
    val random = new Random(1L)
    for {
      a <- IO(random.nextInt)
      b <- IO(random.nextInt)
      _ <- IO(println(("ioByComposition", a, b)))
    } yield (a, b)

  val run: IO[Unit] = {

The Doubly Linked List

Before discussing the deque data structure, it may help to discuss the doubly linked list data structure since their practical applications are often similar. A doubly linked list is a special kind of linked list where each node contains a pointer to the previous node and the next node of the linked list. One of the main ways this data structure differs from the singly list is the latter only has a pointer to the next node. Pointer to null

Below is an example of a doubly linked list node written in the C/C++ programming language:

struct Node { 
  int data; 
  struct Node* next; 
  struct Node* prev; 

Thus an empty node of a doubly linked list can be initialized with the following line of code:

struct Node* head = NULL;

There are three basic insert operations for this type of data structure:

  1. Insert a node at the beginning of the list
  2. Insert a node at the end of the list
  3. Insert a node after another node in the list

There are also three basic operations to delete a node. To do that, the corresponding next and previous pointers of the next-door neighbors of the node to be deleted must be set to null or to the node adjacent to the node to be deleted. Naturally, this is assuming these nodes exist.

Dequeue in Cats Effect

A deque (also called Dequeue) is a double-ended queue that supports stack and queue operations. Part of its appeal is that several operations have a time complexity of only O(1). A practical application of a deque data structure is storing a web browser’s history or software application’s list of undo operations.

Below is a simplification of Scala Cats Effect’s purely functional concurrent implementation of a deque data structure:

trait Dequeue[F[_], A] extends Queue[F, A] {  

def offerBack(a: A): F[Unit]  

def tryOfferBack(a: A): F[Boolean]  

def takeBack: F[A]  

def tryTakeBack: F[Option[A]]  

def offerFront(a: A): F[Unit]  

def tryOfferFront(a: A): F[Boolean]  

def takeFront: F[A]  

def tryTakeFront: F[Option[A]]  

def reverse: F[Unit]  

override def offer(a: A): F[Unit] = offerBack(a)  

override def tryOffer(a: A): F[Boolean] = tryOfferBack(a)  

override def take: F[A] = takeFront  

override def tryTake: F[Option[A]] = tryTakeFront  


Understanding queues and deques is understanding the language we associate with their operations. For example, what is commonly understood as “insert and remove” in the queue and deque world becomes “enqueue and dequeue.” Further, offer is an insert operation, meaning to offer an element is to enqueue or insert an element.

It is a reasonably intuitive implementation. For example, the size method returns the number of elements. The offerFront method enqueues the given element at the front of the queue.

With the Scala Cats Effect implementation, there are two types of Dequeues: bounded and unbounded. That means an offer can be semantically blocked (backpressured) in a bounded Dequeue if it is full.

You may even notice the influence of the Scala Cats Effect Queue that Dequeue extends. For example, Queue’s take method and Dequeue’s takeFront are aliases.

Remember, the Scala Cats Effect Queue’s take method semantically blocks when the queue is empty. Dequeue’s takeFront implementation is conceptually the same but naturally semantically blocks when the Deque is empty.

Below is a snippet of Scala Cats Effect’s Dequeue used in practice.

trait WorkQueue[Work, Result] { 
  def nextRequest: Resource[IO, (Work, Deferred[IO, Result])] 
object WorkQueue { 
  def apply[Request, Response]( 
    requests: Seq[Request], 
    onComplete: Map[Request, Response] => IO[Any] 
  ): IO[WorkQueue[Request, Response]] = 
      requestQueue <- Dequeue.unbounded[IO, Request] 
      _ <- requests.traverse(requestQueue.offer) 
      responses <- IO.ref(Map.empty[Request, Response]) 
      outstandingCount <- IO.ref(requests.size) 
    yield new { 
      override def nextRequest: Resource[IO, (Request, Deferred[IO, Response])] = 
            _ <- outstandingCount.get.flatMap(n => IO.raiseWhen(n == 0)(PieceComplete)) 
            request <- requestQueue.tryTake 
            request <- request match 
              case Some(request) => IO.pure(request) 
              case None          => IO.raiseError(EmptyQueue) 
            promise <- IO.deferred[Response] 
          yield ( 
            (request, promise), 
              bytes <- promise.tryGet 
              _ <- bytes match 
                case Some(bytes) => 
                    _ <- outstandingCount.update(_ - 1) 
                    result <- responses.updateAndGet(_.updated(request, bytes)) 
                    _ <- outstandingCount.get.flatMap(n => IO.whenA(n == 0)(onComplete(result).void)) 
                  yield () 
                case None => 
            yield () 
  case object EmptyQueue extends Throwable 
  case object PieceComplete extends Throwable 

Contact us for more information on Software development with Scala Cats Effect.


  1. Law, Jonathan, and Darren Wilkinson. “Functional probabilistic programming for scalable Bayesian modelling.” arXiv preprint arXiv:1908.02062 (2019).
  2. Law, Jonathan. Scalable bayesian time series modelling for streaming data. Diss. Newcastle University, 2019.
  3. Larsen, Daniel. “Design and Implementation of a Type-safe and Highly Concurrent Runtime System in F.” (2022).
  4. Paju, Jaakko, and Jaakko Järvi. “The modern landscape of managing effects for the working programmer.” management (2023).
  5. Sánchez Fernández, Santiago. “Diseño de sistemas funcionales y reactivos.” (2020).
  6. “Deque - Set 1 (Introduction and Applications) - GeeksforGeeks.” 18 Mar. 2023.”
  7. “Dequeue · Cats Effect -”.
  8. “Dequeue - - F.” Typelevel. Accessed 30 September 2023.
  9. “Introduction to Doubly Linked List – Data Structure … - GeeksforGeeks.” 26 Sept. 2023.
  10. “Data Structure Doubly Linked List - Online Tutorials Library.”.

Related Posts

Leave a Comment