Marvels of functional programming: Composing effects with monads

Monads are simple concepts yet have a notorious reputation of being challenging to comprehend. Despite several articles on monads I am convinced the need for a blog article that addresses monads with the right analogy that is simple and relatable. The box analogy used quite generously to explain monads focuses on the machinery of the monad, the flatmap, instead it should focus on the application of monad.

As an example, it is a difference in an analogy of explaining Linked list as “a data structure with inexpensive remove and add node operation hence fit for modeling fragmented memory (right analogy)” than explaining as “Linked list is data structure with links and nodes(machinery)”

Explaining why composition ends up with box within box situation in the first place is important than getting into bit and bytes of flatten or flatmap which is the solution to the situation. In the next section, we see the marvels composition problem used as a case study. Please refer to programming with effects article which has foundational material on effects.


Marvels composition problem

Our goal is to “suit up” the iron man and launch him. To do this, we need to compose functional calls exposed in 3 modules SuitUp, EngineStart, and Launch.

The following is pseudocode for three modules

Module SuitUp { assembleParts, fuel, suitUp }
Module EngineStart {preLaunchChecks, startEngine}
Module Launch {rangeVerification, launch}

The following is pseudocode for launching

program = Do 
assembleParts andThen
fuel andThen
suitUp andThen
preLauchChecks andThen
startEngine andThen
rangeVerfication andThen
launch

Some of the glaring observations we can make already are the function calls need to happen in the specific order, and each of them could fail. As particular order suggests dependency of a function on the previous one and the possibility of failure represented as an effect this is the perfect problem monads address elegantly.
However, we are arriving at the need of using monads by first exploring, the alternative approaches of solving composition via vanilla functional composition, the conditional checks, the pattern matching, and the functors pattern way.


What are some of the most refreshing problems monads solve?

  • Monads prevent callback hell in Javascript with promises. A promise is a monad.
  • Monads help in composing LINQ queries in C# via SelectMany. IEnumerable is a monad.
  • Monads prevent null runtime exceptions with optional making this a check at compile time on type. Typically the optional type is a monad, but some languages don’t make it.
  • Monads give interactive IO capability in Haskell by composing effects and maintaining referential transparency (via laziness).

Monads Introduction

Monads are patterns used to sequence dependent effectful computations.

Why is this sequencing a big deal? Don’t we write imperative logic all the time where statements get executed one after another?
The reason this is a big deal is, we want this sequencing to be a lambda expression that is a composition of function calls instead of typical imperative style statements.

When the function calls in a lambda expression return an effect like Option[T], it becomes tricky to line up types between function calls in the composition we will soon see in Marvel’s case study. So, monads are tools for composition and breaking problem into tiny functions and composing them is the foundation of functional programming.

If jigsaw, where the application, each of jigsaw blocks are the function calls with edges. These edges are equivalent to an effect type. When effect type is a monad, we can fit the jigsaw perfectly for these kinds of applications.

Jigsaw analogy functions and effects

Before we get into the meat of solving Marvel’s composition problem, I am establishing the foundation on effects in this article and algebraic data types in the next section.


Composition and effects


The algebraic data type (ADT)

An algebraic data type is a composite type made of sum and product type. Product type is available in most languages while sum type is in some languages such as Haskell, Scala, Kotlin and fewer others.

Product type is a record or class type, is a cartesian product of constituents.
 Sum type gives choices similar to enum; however, the critical difference is each choice can be packaged with data with constructor at one end and unpacked with deconstruction with pattern matching at receiving end.

sealed trait Tree[T]       //Tree is either Leaf or branch
case class Leaf[T](value: T) extends Tree[T]
case class Branch[T](left: Tree[T], value: T, right: Tree[T]) extends Tree[T]        //Branch is product of left value and right

Leaf and Branch type expose constructor to construct with specific data. To deconstructor, a pattern match is used as shown in the following map function which transforms each value in Tree with function f by pattern matching tree into either Lead or Branch types.

def map[A, B](tree: Tree[A], f: A => B): Tree[B] = tree match {
case Leaf(value) => Leaf(f(value))
case Branch(left, value, right) => Branch(map(left, f), f(value), map(right, f))
}

API in Scala for marvels composition problem

Following is suit up API.

case class IronSuit(parts: Any)
case class TonyStark()
case class IronMan(parts: Any)
trait SuitUp {
def assembleParts(): Option[IronSuit]
def fuel(ironSuit: IronSuit): Option[IronSuit]
def suitUp(ironSuit: IronSuit, stark: TonyStark): Option[IronMan]
}

We see API is returning an effect of type option as iron man creation could fail and require to happen in a specific order. E.g., fueling occurs after parts assemble.

Suit up

Now let’s define Engine and launch API as follows. After we “suit up” we perform engine start which does prelaunch checks and starts ironman. In Launch module, rangeVerification API returns the coordinates that feed into the Launch API.

case class CoOrdinates(x: Double, y: Double)
trait EngineStart {
def preLaunchChecks(ironMan: IronMan): Option[Unit]
def startEngine(ironMan: IronMan): Option[IronMan]
}
trait Launch extends SuitUp with EngineStart {
def rangeVerification(): Option[CoOrdinates]
def launch(ironMan: IronMan, coOrdinates: CoOrdinates): Option[Unit]
}
Launch Ironman

Now let’s get to the meat of the problem by exploring various approaches to composing launch.


Launch via Function composition

Vanilla functional composition doesn’t work because types don’t line up. The functions expect a Type of order 0 such as A but have a Type of order 1 such as F[A].

Types don’t line up
def api1() : F[A]
def api2(b:A): F[B]
api2(api1()) //Won’t work. api2 wants A but has F[A]
Note: api2 depends on api1

We see this pattern in the Launch API

def assembleParts(): Option[IronSuit]
def fuel(ironSuit: IronSuit): Option[IronSuit]
fuel(assembleParts())//Won’t compile!

Launch via Pattern matching

def api1() : F[A]
def api2(b:B): F[B]

api1() match { //Works
 case 😊=> api2(😊)
 case 😞=> 😞
}

val suitOpt: Option[IronSuit] = api.assembleParts()
val fueledSuit: Option[IronSuit] = suitOpt match {
case Some(suit) => api.fuel(suit)
case None => None
}
Pattern matching fits the jigsaw

Pattern match works, and we can fit the jigsaw perfectly, but we have a problem with the non-idiomatic code.

Following code is a complete program with a pattern matching approach there is a pattern crying to emerge out which is

If value is present in F[A], apply the next api call otherwise return none. We will look at this approach next (the Functor pattern).
val program: Option[Unit] = api.assembleParts() match {
case Some(suit) =>😊
api.fuel(suit) match {
case Some(fueledSuit) =>😊
api.suitUp(fueledSuit, tonyStark) match {
case Some(ironMan) =>😊
api.preLaunchChecks(ironMan) match {
case Some(_) =>😊
api.rangeVerification() match {
case Some(coOrdinates) 😊=> api.launch(ironMan, coOrdinates)
}
case None =>😞 None // range verfication
}
case None =>😞 None //preLaunch checks
}
case None =>😞 None //Suit up
}
case None =>😞 None //fuel
case None =>😞 None //assemble
}

Launch via Functor pattern

The functor is a familiar pattern which solely applies mapper function(A=>B) to fa (F[A]) and produces the result F[B]. This application of map is called lifting mapper into the context of F. Following is the signature of the Functor interface.

trait Functor[F[_]] {
def map[A,B](fa: F[A], mapper: A=>B ):F[B]
}
Functor

A functor is a general interface we can define functor instance for specific effect type such as Option like following.

def map[A, B](fa: Option[A], mapper: A => B): Option[B] =
fa match {
case Some(value) => Option(mapper(value))
case None => None
}

Above definition is nearly what we wanted when we spoke about factoring out repetition in pattern matching example only to discover mapper function in case of our API is not in the form A=>B but A=> F[B] as shown below which results in the F[F[B]] instead of F[B] with application of map.

Situation: mapper function is A=>F[B]

Below is program using functor till we suit up iron man. With every call to map we end up with a layer of Option wrapper. We only need a single F wrapper, and the rest is useless. We need some flattener which we look at next.

val program: Option[Option[Option[IronMan]]] = 
api.assembleParts().map(suit =>
api.fuel(suit).map(fueled =>
api.suitUp(fueled, tonyStark)))
Solving the Jigsaw but in many layers of F

Launch via Functor map and flatten

Let’s define a simple flatten method that removes a layer of Option. The implementation is naive for illustration purposes. Flatten match on fa and return the value inside giving F[A] from F[F[A]]

def flatten[A](ffa: Option[Option[A]]): Option[A] = ffa match {
case Some(fa) => fa
case None => None
}
map followed by Flatten

Below is a program using functor followed by flattening till we suit up iron man. The map followed by flattening works!

val program: Option[IronMan] = 
api.assembleParts()
.map(suit => api.fuel(suit)
.map(fueled => api.suitUp(fueled, tonyStark)))
.flatten
.flatten
map followed by flatten fits the jigsaw

Map followed by flattening function call is abstracted out as a single function called flatmap in a monad interface we define next.


Launch with Monad

Let’s define a generic interface for monad and implement an instance for Option

trait Monad[F[_]] extends Applicative[F] {
def flatMap[A,B](fa: F[A])(f: A => F[B]): F[B]
}
Flatmap monads machinery

Let’s define flatmap for Option effect type

override def flatMap[A, B](fa: Option[A])(f: A => Option[B]): Option[B] =
fa match {
case Some(value) => f(value)
case None => None
}

Let’s apply flatmap till we suit up ironman, and it works.

Flatmap nests lambda giving a functional equivalent of sequencing
Examining closely we see monads via flatmap operation nest the subsequent API calls as lambda giving a functional equivalent of Sequencing dependant computation.

If you have followed till now, you should celebrate the moment with a good break and probably a craft beer as monads are one of the essential tools in functional programming.

Most languages have syntactic sugar via language syntax to nest this flatmap calls. Scala has for comprehension, and Haskell “do” blocks. Below is the entire program for launching in a for comprehension.

val program: Option[Unit] = for {
suit <- api.assembleParts()
fueledSuit <- api.fuel(suit)
ironMan <- api.suitUp(fueledSuit, tonyStark)
_ <- api.preLaunchChecks(ironMan)
ordinates <- api.rangeVerification()
_ <- api.launch(ironMan, ordinates)
} yield ()

Monads in Haskell

In purely functional programming languages like Haskell, monads with laziness make the side effects pure (side effects become value or description). The side effects such as interactive input-output at any stage in an application are wrapped in an IO monad. IO Monads do not perform input-output but return this side effect as value to the outer edge (i.e., the main block) as value or description. It is in the Main block the side effects are executed. The main block is called the end of the world or edge of the world, and side effects are okay here as there is no other code to observe it. This concept is slightly hard to sink in first, so it is okay if you don’t get it. Today we are in mission to understand monads so we can discount the purity and look at purity in later articles with IO monad.

The most important take away is monads work with laziness to keep every haskell program referentially transparent, which is an important property for purely functional programming.

Conclusion

As we say, Monad is a pattern to sequence-dependent functional calls that return an F[A] or similar higher order structure. Monads are tools for doing imperative logic in functional programming. In future articles, we look at laws, abstracting effect type, applicative functors, and other marvelous topics.

Bibliology:

  • Scala with cats by underscore.
  • The red book.
  • Programming in Haskell Hutton.
  • The Haskell book.

Credits ( for Images):

https://i.pinimg.com/originals/ea/30/9e/ea309ec4127773d8a963e9e1a9076dee.gif

http://pluspng.com/puzzle-png-hd-8341.html