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:
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.
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:
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:
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:
Now that we understood the beta reduction, lets apply this concept to all our methods:
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:
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:
Ok now lets have a look on how all our program looks like:
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:
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:
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.