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:
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:
Thus an empty node of a doubly linked list can be initialized with the following line of code:
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:
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.