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 AlkebuLan
 01 October 2023
Check out Yadu Krishnan's latest #Scala blog post!
— Scala Jobs (@ScalaJobsDev) September 27, 2023
Learn how to create a customized retry policy with error handling using the CatsRetry library.https://t.co/JkwiQ31SZM
Table of Contents
 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 highlevel, statically typed, compiled, and garbagecollected programming language. Unlike Haskell, Scala is not only functional but also objectoriented.
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 builtin 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 nextdoor 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 doubleended 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
}
Contact us for more information on Software development with Scala Cats Effect.
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 Typesafe 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.”.
userexperience
Our Drupal Web Development Servicesdigitalexperienceplatform
Some Digital Experience Platforms Use the OSGi Framework