Friday 1 June 2012

Rework: Monads in Scala - 3

Today we will speak more about flatMap, Monadic Zero and other steps.

Let's start from the Business. Should I use Monads?

Its good to start with Scala's Option class, but while we are still don't understand the theory, lets reinvent the wheel to drive into details. Additionally we will try to follow Function and Object Oriented best practices and won't do optimizations etc, while we are not implementing library.

Imagine the machine, which can give response to any question. Any puzzle in this Galaxy can be given return. Everything is clean and Zen came... Or not, is human/android/anything except God able to understand the responses? Of corse not!

Any response from the system can be comprehend by Human (system's user) or not. Lets introduce some abstraction: Response. Response is return/answer from the system. Response can be presented by Answer (contains clean answer from the System)  or Marvelous (we didn't get it and won't feel/read/hear it to present in any Human friendly state, it's like infinity in mathematics, untouchable).
Response is declaration and it's useless without been used (mapped to something). If it's comes as a knowledge we can map it to a string, to make it readable etc.

Moving far from crazy story to design and implementation: Response is the abstract class just to declare some functionality: 
  1. it is container
  2. it may have valid value or not)
  3. we can apply some function to value and keep it wrapped in Response via map method

Monad in OOP

Drawing the code:

    sealed abstract class Response[+A](val isStable: Boolean) {
      def value: A
      def map[B](func: A => B): Response[B]
    }

This almost follows previous lesson best implementation for Monad - except abstract declaration. We are using it to to just declare functionality. Remember that Response is two-faced: Answer or Marvelous.
Declaring them as separate case classes adds a Pattern Matching Magic to our Monad. This we will review on next sessions.
Lets start from the Answer:

    final case class Answer[+A](value: A) extends Response[A](true){
        def map[B](func: A => B) = new Answer(func(value))
    }

we are declaring that Container is immutable, map just applies a method and wraps it to response.

FlatMap

Let's add a problems to our business: we got some feasible Answer and trying to map it (for example write down, add text or just a sign as song. Or even worse, we got something and mapping it to Mathematics - because isn't everything is covered by modern Mathematics - result should be still wrapped with Answer, because it can be an answer to Mathematics or can be useless here:

    val toMath = (in:String) => new Answer(in.toInt)
    val box = new Answer("5") map toMath //Returns Answer(Answer(5)))

Applying map that return new Monad inside bring to incapsulated Monad in Monad:
    M(M(M(...M(value))...)))

This is not easy to use and there was flatten method introduced, to unwrap the Monad:

    def flatten[B](outer: Response[Response[B]]): Response[B]


Scala does not require you to write flatten explicitly. But it does require that each monad have a method called flatMap.


    final def flatMap[B](f: A => Response[B]): Response[B] = flatten(map(f))
    This is exactly the Functor from the first lessons
    (A => M[B] ) => (M[A] => M[B]) //Functor

As we can find there is a connection law between map and flatMap. Another one not required by Scala monadic function is unit. It's just a way how to create a Monad - for example unit v in Scala can be:
    new M(v)
or using sugar with apply method
    M(v)

With help of unit we can declare map via flatMap:

    class M[A](value: A) {
       private def unit[B] (value : B) = new M(value)
       def map[B](f: A => B) : M[B] flatMap {x => unit(f(x))}
       def flatMap[B](f: A => M[B]) : M[B] = ...
     }

Connection law between map and flatMap is:
    m map f ≡ m flatMap {x => unit(f(x))}
And finally we are getting the code:
    sealed abstract class Response[+A](val isStable: Boolean) {
        def value: A
        def map[B](func: A => B): Response[B]
        def flatten[B](outer: Response[Response[B]]): Response[B]
        final def flatMap[B](f: A => Response[B]): Response[B] = flatten(map(f))
    }

    final case class Answer[+A](value: A) extends Response[A](true) {
       def map[B](func: A => B) = new Answer(func(value))
       def flatten[B](outer: Response[Response[B]]) = outer.value
    }

As U can find Monad and Functor are the same (connected by law) and placed in the same class. This is not pure Function Programing style - but this is what Scala expects from us. Flatten and unit methods aren't mandatory and can be imbedded into others.

If U still have a power there more examples to prove The First Monad Law: Identity

    m flatMap unit ≡ m // or equivalently
   m flatMap {x => unit(x)} ≡ m
and The Second Monad Law: Unit
    unit(x) flatMap f ≡ f(x) // or equivalently
    unit(x) flatMap {y => f(y)} ≡ f(x)
and The Third Monad Law: Composition
    m flatMap {x => g(x)} flatMap {y => f(y)} ≡      
         m flatMap {x => g(x) flatMap {y => f(y) }}




No comments:

Post a Comment