Skip to content

Monads

Jump to bottom
Rohit edited this page Jan 3, 2017 · 20 revisions

Recap: flatMap

flatMap is a combinator that combines mapping and flattening. flatMap takes a function that works on the nested lists and then concatenates the results back together.

         map with A => M[B]                   flatten
M[A]  -------------------------->  M[M[B]]  -----------> M[B]

Examples:

// Example 1
val nestedNumbers = List(List(1, 2), List(3, 4))
nestedNumbers.flatMap(x => x.map(_ * 2)) //Output: List(2, 4, 6, 8)

// Example 2
val fruits = Seq("apple", "banana", "orange")
fruits.map(_.toUpperCase)             // List(APPLE, BANANA, ORANGE)
fruits.map(_.toUpperCase).flatten     // List(A, P, P, L, E, B, A, N, A, N, A, O, R, A, N, G, E)
fruits.flatMap(_.toUpperCase)         // List(A, P, P, L, E, B, A, N, A, N, A, O, R, A, N, G, E)

Monads

Data structures with map and flatMap seem to be quite common. In fact there’s a name that describes this class of a data structures together with some algebraic laws that they should have. They are called monads.

A monad M is a parametric type M[T] with two operations, flatMap and unit, that have to satisfy some laws.

trait M[T] {
    def flatMap[U](f: T => M[U]): M[U]
}

def unit[T](x: T): M[T]

In the literature, flatMap is more commonly called bind.

Examples:

  • List is a monad with unit(x) = List(x)
  • Set is monad with unit(x) = Set(x)
  • Option is a monad with unit(x) = Some(x)
  • Generator is a monad with unit(x) = single(x)

flatMap is an operation on each of these types, whereas unit in Scala is different for each monad.

Maps and Monads

map can be defined for every monad as a combination of flatMap and unit:

m map f == m flatMap (x => unit(f(x)))
// OR
m map f == m flatMap (f andThen unit)

Monad Laws

To qualify as a monad, a type has to satisfy three laws:

  1. Associativity:
m flatMap f flatMap g == m flatMap (x => f(x) flatMap g)
  1. Left unit:
unit(x) flatMap f == f(x)
  1. Right unit:
m flatMap unit == m

Try

Try is similar to Option. Where Option can have a value of something or none, Try can have a value of Success or Failure. It uses Java try in its implementation.

Whereas Option is a monad, Try is not since the left unit law fails.

Bullet-proof principle: An expression composed from Try, map, flatMap will never throw a non-fatal exception.

Conclusion:

We have seen that for-expressions are useful not only for collections. Many other types also define map, flatMap, and withFilter operations and with them for-expressions.

Examples: Generator, Option, Try.

Many types that define flatMaps are Monads. If they also define withFilter, then they are called Monads with Zero.

The three monad laws give useful guidance in the design of library APIs

Understanding

Monad is a concept or a design pattern, that simply defines a way of composing data. It is commonly used in functional programming languages. The motivation is to declutter code.

Consider tha Java code where we have 3 classes. Foo embeds Bar which embeds Baz which embeds the compute method. The bottleneck here is any of these embedded instances can be null, so a typical way we would cope with this with multiple null checks. And note that since we are returning a null the return type cannot be int and has to be Integer.

public class Foo {
    public Bar getBar();
}
public class Bar {
    public Baz getBaz();
}
public class Baz {
    public int compute();
}

public Integer compute(Foo foo) {
    if (foo != null) {
        Bar bar = foo.getBar()
        if (bar != null) {
            Bar baz = bar.getBaz()
            if (baz != null) {
                return baz.compute
            } else {
                return null
            }
        } else 
            return null;
        }
    } else 
        return null
}

The same code can be written in Scala as below:

class Foo {
    def bar : Bar
}
class Bar {
    def baz : Baz
}
class Foo {
    def compute : Int
}

def compute(foo: Foo): Int = {
    if (foo != null) {
        val bar = foo.bar
        if (bar != null) {
            val baz = bar.baz
            if (baz != null) {
                baz.compute
            } else {
                null
            }
        } else 
            null;
        }
    } else 
       null
}

As you can see, it is not better than the Java code. This is where we want to use Monads to declutter the code.

Hence we define a Monad:

trait Monad[A] {
    def map[B](f: A => B): Monad[B]
    def flatMap[B](f: A => Monad[B]): Monad[B]
}

This trait provides a standard way of composing and sequencing operations on some contained values.

  • map: applies a regular function to the contained values
  • flatMap: applies a "monadic" function to the contained values

Now we define the option Monad (differs from the scala.Option type, but works similarly)

trait Option[A] 

case class Some[A](a: A) extends Option[A]
case class None[A] extends Option[A]

Now we define the map and flatMap to make type Option into a Monad:

trait Option[A] {
    def map[B](f: A => B): Option[B]
    def flatMap[B](f: A => Option[B]): Option[B]
}

case class Some[A](a: A) extends Option[A] {
    def map[B](f: A => B): Option[B] = {
        Some[f(a)]
    }
    def flatMap[B](f: A => Option[B]): Option[B] = {
        f(a)
    }
}
case class None[A] extends Option[A] = {
    def map[B](f: A => B): Option[B] = {
        None
    }
    def flatMap[B](f: A => Option[B]): Option[B] = {
        None
    }
}

So going back to the initial cluttered example,

class Foo {
    def bar : Option[Bar]
}
class Bar {
    def baz : Option[Baz]
}
class Foo {
    def compute : Int
}

def computeBaz(baz: Baz): Int = {
    baz.compute
}
def computeBar(bar: Bar): Option[Int] = {
    bar.baz.map{ computeBaz } 
}
def computeFoo(foo: Foo): Option[Int] = {
    foo.bar.flatMap{ computeBar }     
}
def compute(maybefoo: Option[Foo]): Option[Int] = {
    maybefoo.flatMap{ computeFoo }
}

This still looks very cluttered. This can be further simpliefied as:

def compute(maybefoo: Option[Foo]): Option[Int] = { 
    maybefoo.flatMap { foo => 
        foo.bar.flatMat { bar =>
            bar.baz.map { baz =>
                baz.compute
            }
        }
    }
}

This can be further simplified using a for expression which internally uses the map and flatMap functions to provide syntactic sugar:

def computeAll(maybefoo: Option[Foo]): Option[Int] = { 
    for {
         foo <- maybefoo
         bar <- foo.bar
         baz <- bar.baz
     } yield baz.compute
}

We can also use a List instead of an Option above, which is by default a monad in scala.

class Foo {
    def bars : List[Bar]
}
class Bar {
    def bazs : List[Baz]
}
class Foo {
    def compute : List[Int]
}

def computeAll(foos: List[Foo]): List[Int] = { 
    for {
         foo <- foos
         bar <- foo.bars
         baz <- bar.bazs
     } yield baz.compute
}

Some reading:

Week 1

Week 2

Week 3

Week 4

Clone this wiki locally