[Coursera FP] W1 - L4 - Monads

Source From Here 
Monads 
Data structures with map and flatMap seem to be quite common. In fact there's a name that describe 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. 

view plaincopy to clipboardprint?

1. train M[T]{  
2.     def flatMap[U](f: T=> M[U]):M[U]  
3. }  
4. def unit[T]:(x:T): M[T]  

In the literature, flatMap is more commonly called bind. 

Example of Monads 

* List is a monad with unit(x) = List(x)
* Set is a 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. 

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

view plaincopy to clipboardprint?

1. m map f == m flatMap (x => unit(f(x))) == m flatMap(f andThen unit)  

Monad Laws 
To qualify as a monad, a type has to satisfy three laws: 
* Associativity 

view plaincopy to clipboardprint?

1. m flatMap f flatMap g == m flatMap (x => f(x) flatMap g)  

* Left unit 

view plaincopy to clipboardprint?

1. unit(x) flatMap f == f(x)  

* Right unit 

view plaincopy to clipboardprint?

1. m flatMap unit == m  

Take List for example: 

view plaincopy to clipboardprint?

1. val x = 1  
2. val m = List(1)  
3. val unit:Int=>List[Int] = x => List(x)  
4. val f:Int=>List[Int] = x=>List(x+1)  
5. val g:Int=>List[Int] = x=>List(x*2)  
6. val list = List(1,2,3,4)  
7. val a1 = list flatMap f flatMap g  
8. val a2 = list flatMap {x => f(x) flatMap g}  
9. printf("Satisfy Associatity Law? %s\n", a1 == a2)  
10.   
11. // unit(x) flatMap f == f(x)      
12. val l1 = unit(x) flatMap (f)  
13. printf("Satisfy Left Unit Law? %s\n", l1 == f(x))  
14.   
15. // m flatMap unit == m      
16. val r1 = m flatMap unit  
17. printf("Satisfy Right Unit Law? %s\n", r1 == m)  

Checking Monad Laws 
Let's check the monad laws for Option. Here's flatMap for Option: 

view plaincopy to clipboardprint?

1. abstract class Option[+T]{  
2.     def flatMap[U](f:T=>Option[U]):Option[U] = this match {  
3.         case Some(x) => f(x)  
4.         case None => None  
5.     }  
6. }  

- Left Unit Raw 
Need to show Some(x) flatMap f == f(x) 

- Right Unit Raw 
Need to show: opt flatMap Some == opt 

- Associative Law 
Need to show: opt flatMap f flatMap g == opt flatMap (x => f(x) flatMap g) 
Let's check in with code review: 

view plaincopy to clipboardprint?

1. // Checking Monad Raw  
2. val f2:Int=>Option[Int]=x => Option(x+1)  
3. val g2:Int=>Option[Int]=x => Option(x*2)  
4. val map = Map[String,Int]("john"->18, "mary"->20, "ken"->19)  
5. val opt = map get ("john")  // opt is type of Option  
6. printf("opt with type=%s\n", opt.getClass.getName)  
7.   
8. // Checking Left Unit Raw: unit(x) flatMap f == f(x)   
9. val lur = opt flatMap f2    
10. printf("Satisfy Left Unit Law? %s (%s)\n", lur==f2(opt.getOrElse(-1)), lur)  
11.   
12. // Checking Right Unit Raw: opt flatMap Some == opt  
13. val optUnit:Int=>Option[Int]=x=>Option(x)  
14. val rur = opt flatMap optUnit  
15. printf("Satisfy Right Unit Law? %s (%s)\n", rur==opt, rur)  
16.   
17. // Checking the Associative Law: opt flatMap f flatMap g == opt flatMap (x => f(x) flatMap g)  
18. val asr = opt flatMap f2 flatMap g2  
19. printf("Satisfy Association Law? %s (%s)\n", asr == (opt flatMap(x => f2(x) flatMap g2)), asr)  

Significance of the Laws for For-Expressions 
We have seen that monad-typed expressions are typically written as for expressions. What is the significance of the laws with respect to this? 
1. Associativity says essentially that one can “inline” nested for expressions: 

2. Right Unit Raw Says 
Intuitively: 

3: Left unit does not have an analogue for for-expressions. 

Another type: Try 
In the later parts of this course we will need a type named Try. Try resembles Option, but instead of Some/None there is a Success case with a value and a Failure case that contains an exception: 

view plaincopy to clipboardprint?

1. abstract class Try[+T]  
2. case class Success[T](x:T) extends Try[T]  
3. case class Failure[T](ex:Throwable) extends Try[Nothing]  

Try is used to pass results of computations that can fail with an exception between threads and computers. 

Creating a Try 
You can wrap up an arbitrary computation in a Try. 

view plaincopy to clipboardprint?

1. Try(expr) // gives Success(someValue) or Failure(someException)  

Here’s an implementation of Try: 

view plaincopy to clipboardprint?

1. object Try {  
2.   def apply[T](expr: => T):Try[T]=   
3.     try Success(expr)  
4.     catch{  
5.       case NonFatal(ex) => Failure(ex)  
6.     }    
7. }  

Composing Try 
Just like with Option, Try-valued computations can be composed in for expresssions. 

If computeX and computeY succeed with results Success(x) and Success(y), this will return Success(f(x, y)). If either computation fails with an exception ex, this will return Failure(ex). 

Definition of flatMap and map on Try 

view plaincopy to clipboardprint?

1. abstract class Try[+T] {  
2.   def flatMap[U](f: T => Try[U]): Try[U] = this match {  
3.     case Success(x) => try f(x) catch { case NonFatal(ex) => Failure(ex) }  
4.     case Failure(ex) => Failure(ex)  
5.   }  
6.   def map[U](f: T => U): Try[U] = this match {  
7.     case Success(x) => Try(f(x))  
8.     case Failure(ex) => Failure(ex)  
9.   }  
10. }  

So, for a Try value t, 

view plaincopy to clipboardprint?

1. t map f == t flatMap (x => Try(f(x))) == t flatMap (f andThen Try)  

It looks like Try might be a monad, with unit = Try. Is it? It turns out the left unit law fails. 

view plaincopy to clipboardprint?

1. Try(expr) flatMap f != f(expr)  

Indeed the left-hand side will never raise a non-fatal exception whereas the right-hand side will raise any exception thrown by expr or f. Hence, Try trades one monad law for another law which is more useful in this context: 

An expression composed from ‘Try‘, ‘map‘, ‘flatMap‘ will never throw a non-fatal exception.

Call this the “bullet-proof” principle. 

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 of the types defining flatMap are monads. (If they also define withFilter, they are called “monads with zero”). The three monad laws give useful guidance in the design of library APIs.