程式扎記: [Coursera FP] W1 - L4 - Monads

標籤

2016年9月10日 星期六

[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. 
  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
  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 
  1. m flatMap f flatMap g == m flatMap (x => f(x) flatMap g)  
* Left unit 
  1. unit(x) flatMap f == f(x)  
* Right unit 
  1. m flatMap unit == m  
Take List for example: 
  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
  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: 

  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 TryTry resembles Option, but instead of Some/None there is a Success case with a value and a Failure case that contains an exception: 
  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
  1. Try(expr) // gives Success(someValue) or Failure(someException)  
Here’s an implementation of Try
  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 
  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
  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
  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 mapflatMap, 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.

沒有留言:

張貼留言

網誌存檔