Pages

Saturday 13 December 2014

Demistify the State Monad with Scala 1/2

In this post I would like to introduce the concept of Monad with a simple example.

Ok lets start...

Let's create a data structure for Stacks and in pure functional programming style having methods to push and pop elements into the stack.

Step 1: we can use the List to implement a Stack:


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
package fp

object StackApp extends App {

  type Stack[A] = List[A]
  
  def push[A](a:A, stack:Stack[A]): Stack[A] = a :: stack
  
  def pop[A](stack:Stack[A]): (Option[A], Stack[A]) = stack match {
    case a :: tail => (Some(a), tail)
    case Nil       => (None, Nil)
  }
  
}

Because we have immutable data, methods push and pop have to return a new Stack after a push and pop operation on the input stack.

Now lets assume we want to define a new business method, called: popPairs, this method accept a stack and try to pop 2 elements, the result will be a tuple of Option[A] and the new stack after the pop operation.


1
2
3
4
5
  def popPairs[A](stack:Stack[A]): ((Option[A], Option[A]), Stack[A]) = {
    val (opt1, stack1) = pop(stack)
    val (opt2, stack2) = pop(stack1)
    ((opt1, opt2), stack2)
  }


Ok now lets try to use our methods and see how we can build new functions from existing ones.
I want a function pushZero which given a stack of Int will add a 0 on top of the stack and I want to reuse the push function. In order to do that I must use Currying syntax in scala and I have to modify the push signature as per below:


1
2
3
4
5
6
7
def push[A](a:A)(stack:Stack[A]): Stack[A]  = a :: stack
...
val pushZero = push(0)(_)
...
val myStack:Stack[Int] = 1::2::3::Nil

val newStack = pushZero(myStack)

The key question here is: what's the type of the val pushZero ?
pushZero is like push where the first argument of the function has been already passed but didn't get yet the second.

The only possible answer to that question is: pushZero: Stack[Int] => Stack[Int]

The call to push(0)(_) will return a new function which only require a Stack[Int] argument to be passed in order to produce a new Stack.

Finally in line 7 we will get the final result, so pushZero is just delaying the execution of pop once all the parameters have been provisioned.

Based on the above I personally prefer not do adopt the Scala Currying syntax and like in Haskell be more honest on the function signature, in fact with a simple trick we can move the Stack[A] parameter on the right side of the colon, making it part of the return type:


1
def push[A](a:A):  Stack[A] => Stack[A]  = stack => a :: stack

So now push accept one argument of type A and return a function that accept a Stack[A] and returns a Stack[A]. The implementation of the function is a lambda expression which will pre-append the a:A element.
Note:  the lambda expression accept as input parameter the stack, but in the body we also use the a:A value coming from the push signature, this mechanism is called closure.

After this change also the currying syntax will become more elegant and the code we have seen in the previous block will now look like this:


1
2
3
4
5
6
7
def push[A](a:A):  Stack[A] => Stack[A]  = stack => a :: stack
...
val pushZero = push(0) // pushZero is type of Stack[Int] => Stack[Int]
...
val myStack = 1::2::3::Nil

val newStack = pushZero(myStack)

Now that we understood the beta reduction, lets apply this concept to all our methods:


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
package fp

object StackApp extends App {

  type Stack[A] = List[A]
  
  def push[A](a:A) : Stack[A] => Stack[A] = stack => a :: stack
  
  def pop[A]: Stack[A] => (Option[A], Stack[A]) = {
    case a :: tail => (Some(a), tail)
    case Nil       => (None, Nil)
  }
  
  def popPairs[A]: Stack[A] => ((Option[A], Option[A]), Stack[A]) = stack => {
    val (opt1, stack1) = pop(stack)
    val (opt2, stack2) = pop(stack1)
    ((opt1, opt2), stack2)
  }
}

Something to note here is the change in line 9. pop[A] is a partial function. The concept is very similar to the Erlang language, so this function will do pattern matching on its arguments using the case statement in the body. If the input parameter doesn't match with any of the case statement, an exception will be thrown.

Essentially these 2 syntaxes are equivalent:


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def pop[A]: Stack[A] => (Option[A], Stack[A]) = {
    case a :: tail => (Some(a), tail)
    case Nil       => (None, Nil)
  }

// is equivalent to:

def pop[A]: Stack[A] => (Option[A], Stack[A]) = stack => stack match {
    case a :: tail => (Some(a), tail)
    case Nil       => (None, Nil)
  }

But as you can see the second pop[A] definition declare an input parameter stack that is just be used in a match statement, there is no real need to have the stack input variables so Scala optimise this syntax by using the concept of Partial Functions.

Ok now that all our functions went through the beta reduction, lets reason on their signatures. First of all the push function is a setter method, is in essence a method that modify an object without returning a new value. Because we like honest functions and more importantly to make the signature consistent with the other methods we can say that push will return a tuple of (Unit, Stack[A]), where the first element of the tuple is the result of this operation (void in scala = Unit) and the second is the new status of the stack:


def push[A](a:A): Stack[A] => (Unit, Stack[A]) = stack => ((), a :: stack)

Ok now lets have a look on how all our program looks like:


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
package fp

object StackApp extends App {

  type Stack[A] = List[A]
  
  def push[A](a:A) : Stack[A] => (Unit, Stack[A]) = stack => ((), a :: stack)
  
  def pop[A]: Stack[A] => (Option[A], Stack[A]) = {
    case a :: tail => (Some(a), tail)
    case Nil       => (None, Nil)
  }
  
  def popPairs[A]: Stack[A] => ((Option[A], Option[A]), Stack[A]) = stack => {
    val (opt1, stack1) = pop(stack)
    val (opt2, stack2) = pop(stack1)
    ((opt1, opt2), stack2)
  }
}

Have a look on the return type of our methods, they share a common pattern.
All of them accept the current status (Stack[A]) and they return as result a tuple where the first element is the  result of the method application and the second element is the new status ( the new Stack[A] after the function has been applied).

So we can define a new entity which we will call State[S, A] as the following:


type State[S, A] = S => (A, S)

State[S, A] is just an alias for a function that given an S return a (A, S).
Lets apply State on our function return types:


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
package fp

object StackApp extends App {

  type Stack[A] = List[A]
  type State[S, A] = S => (A, S)
  
  def push[A](a:A) : State[Stack[A], Unit] = stack => ((), a :: stack)
  
  def pop[A]: State[Stack[A], Option[A]] = {
    case a :: tail => (Some(a), tail)
    case Nil       => (None, Nil)
  }
  
  def popPairs[A]: State[Stack[A],(Option[A], Option[A])] = stack => {
    val (opt1, stack1) = pop(stack)
    val (opt2, stack2) = pop(stack1)
    ((opt1, opt2), stack2)
  }
}

Fantastic, so State is nothing else than an alias of a function that given the current status will produce a result of type A and a new status.

What can we do with State ?

Well the power of programming is composition, the ability to combine different operations together in order to obtain our target result.
My target is to avoid to write the code inside popPairs, that code is error prone because I have to be careful to always look at the stack returned by the previous function call and use it in the new expression.

Now that we have introduced the concept of state, on the next post we will see how we can define operations over the State[S, A] and how to promote it from a type alias to a Type Class (Trait).

Continue to read the second part here.

2 comments:

  1. > Well the power of programming is composition, the ability to combine different operations together in order to obtain our target result.

    Thanks for this enlightening post. It helped me to understand the State monad.

    ReplyDelete
  2. Really well explained. Thank a lot.

    ReplyDelete