What is a doubly linked list

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.

By Mensah Alkebu-Lan
01 October 2023

Doubly Linked List and the Scala Cats Effect Dequeue

Check out Yadu Krishnan's latest #Scala blog post!

Learn how to create a customized retry policy with error handling using the Cats-Retry library.https://t.co/JkwiQ31SZM
— Scala Jobs (@ScalaJobsDev) September 27, 2023

Overview of Scala and Monads
An Introduction to Scala Cats Effect
The Doubly Linked List
Dequeues in Scala Cats Effect
References

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] = {
    ioByVariable.guarantee(ioByComposition)
  }
}

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:

Insert a node at the beginning of the list
Insert a node at the end of the list
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]] = 
    require(requests.nonEmpty) 
    for 
      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])] = 
        Resource( 
          for 
            _ <- 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), 
            for 
              bytes <- promise.tryGet 
              _ <- bytes match 
                case Some(bytes) => 
                  for 
                    _ <- outstandingCount.update(_ - 1) 
                    result <- responses.updateAndGet(_.updated(request, bytes)) 
                    _ <- outstandingCount.get.flatMap(n => IO.whenA(n == 0)(onComplete(result).void)) 
                  yield () 
                case None => 
                  requestQueue.offerFront(request) 
            yield () 
          ) 
        ) 
    } 
 
  case object EmptyQueue extends Throwable 
  case object PieceComplete extends Throwable 
} 

References

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