SCALA: The power of Lambda-Type in Higher kinded types

In the previous posts we have explored the type classes, we have defined the Semigroup type class in this post and then we have exploited the State Monad.

I would like to start this post from the definition we have done on the State Monad:

  trait State[S, A] {
    def apply(s:S): (A, S)
    def map[B](f:A=>B): State[S, B] = State { s =>
        val (a, s2) = this(s)
        (f(a), s2)
    }
    def flatMap[B](f:A=>State[S, B]): State[S, B] = State { s=>
      val (a, s2) = this(s)
      f(a)(s2)
    }
  }
  
  object State {
    def apply[S, A](f: S=>(A, S)) = new State[S, A] {
      def apply(s:S) = f(s)
    } 
  }

Without talking about Category Theory lets understand what make the above trait a Monad.

Monad is essentially a container of other types and it defines some transformation methods between different contained types.
Because this can get quite confusing by using words lets use code to explain it:

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

Quite interesting... Monad is nothing else that a trait which defines map and flatMap across container types (If you want to dig down to the math behind that then Category Theory is what you need to look for).

I would like now to re-define State as a member of Monad, something like: Monad[State[S, A], A] ...

Lets try it:

  trait Monad[M[A], A] {
    def map[B](f: A=>B): M[B]
    def flatMap[B](f: A=>M[B]): M[B]
  }
  
  trait State[S, A] {
    def apply(s:S): (A, S)
  }
  
  object State {
    def apply[S, A](f: S=>(A, S)) = new State[S, A] {
      def apply(s:S) = f(s)
    } 
  }

Ok so now we have moved map and flatMap methods away from State and created a new trait for Monad. We want now State to be a member of Monad so it can inherit map and flatMap.
Ideally we would like to do something like that:

  object Monad {
    implicit def stateMonad[S, A](sm:State[S, A]) = new Monad[State[S, A], A] {
      def map[B](f:A=>B) = State[S, B] { s => 
        val(a, s2) = sm(s)
        (f(a), s2)
      }
      
      def flatMap[B](f: A=>State[S,B]) = State[S, B] { s =>
       val (a, s2) = sm(s)
       f(a)(s2)
      }
    }
  }

The sad part of the above code is that Line 2 will NOT COMPILE!

In fact the Monad trait accept a type M[_] and not M[_ , _] !!!!

Obviously I can go and change the Monad trait definition but then it will not work for container with single type and so on....

We need to do some magic and transform State[S, A] in something with only one type parameter but without loosing in "Generalisation".

That's where we use Lambda-types. Have a look on the below code:

  object Monad {
    implicit def stateMonad[S, A](sm:State[S, A]) = new Monad[({type λ[A]=State[S,A]})#λ, A] {
      def map[B](f:A=>B) = State[S, B] { s => 
        val(a, s2) = sm(s)
        (f(a), s2)
      }
      
      def flatMap[B](f: A=>State[S,B]) = State[S, B] { s =>
       val (a, s2) = sm(s)
       f(a)(s2)
      }
    }
  }

I know what you are thinking right now... WTF.... At least that was my first reaction when I have seen Lambda-types for the first time.

What's going on line 2 ?
I had to do 2 things:

Transform State[S, A] into a type wit single parameter: λ[A]
Don't loose the constraint of type S, so using a sort of closure on the type definition.

So what we have said is that we want λ[A] to be an alias for State[S, A] and because λ[A] is of type M[_] the compiler is not complaining. Note that I couldn't define the type λ in another expression because the definition of λ is using the type S, so if you remember our talk about closure on function parameters here we see the same trick but used on types, isn't that cool?

Pages

Wednesday, 17 December 2014

The power of Lambda-Type in Higher kinded types

No comments:

Post a Comment