# Option Monad - From Scratch

In a post About Monads - a gentle introduction I have introduced a concept of monad. Since now we should have a good intuition what monad is and be aware of the situations where it can be used to simplify the code and make it more readable.

In this post we will focus on an Option monad which wraps value in a context aware of whether or not the value exists. We will start with a problem and solution not exactly suiting our needs and by adapting Option monad we will try to fix this.

## Problem

There are 3 streams of numbers given as a strings.

After zipping and flattening we got a stream called data containing tuples of 3 strings

Our task is to build a pipeline that generates a stream of Doubles which is a result of division one number by another in a sequence in the context of the same tuple.

It means that the pipeline for a stream described as

should generate a stream of numbers given by formula mentioned below

This problem can be solved using following scala code

div function is defined in DivModule

For a streams of numbers defined at the beginning we should get

The numbers are correct, but take a look on implementation of a parse and div functions. Those functions are not total. In functional world a function which is not total is called partial. A partial function is not defined for all values passed as its arguments.

And for following streams of numbers

after running pipeline we get an Exception

We can easily fix this by lifting a partial function to a total function. Let’s add lift function to the DivModule

and modify the pipeline accordingly

Now pipeline generates streams of numbers like

We can spot that for each undefined value we get -1 because of lift function which maps all undefined values to the default one, in our case -1.

In order to get only a valid numbers let’s apply a filter

and our result is

For a first look this solution would seem to be good, but what about all variations of streams for which pipeline could return -1 as a correct result ?

For example, when we change fifth number in zs from 3 to -3

our pipeline will generate

This is wrong and changing a default value in lift function doesn’t fix this, because for each such case we can find a counterexample where a correct value is filtered out. It is easy to prove that div function returns numbers from the whole Double space. In category theory there is a name for such functions (morphisms) - epimorphisms.

And here an Option monad comes to the rescue.

In order to implement an Option monad let’s start with defining a data type constructor

Option is an algebraic data type constructor parametrized with A in a co-variant position. We can think of an Option[_] like about container keeping a value. For now it has no context.

Let’s assigned a context to it by defining a value constructor called Some

This constructor introduced a context of container with a none empty value.

A context meaning no value (empty container) can be defined with None

None reveals why we need a type parameter A to be in co-variant position - we simply requires None to be cast to any Option[A].

Recalling a definition of Monad we know that it consists of three parts:

• type constructor M[A]
• type converter (called unit, pure or return)
• combinator (called bind, >>= or flatMap)

First part is fulfilled. Now we have to implement type converter - pure

pure is a function which is responsible for putting a given value to the minimal meaningful context. For Option we requires that each non null value should be bind to the Some, in other case it should be None.

The toughest to implement is a combinator function called flatMap. For an Option it is very easy task however.

This higher order function is very powerful and can be used as a primitive to implement for example map and filter in a following way

Thanks to the flatMap we are able to get a value from container, abstracting whether or not the value exists or not, and apply a map transformation deciding if we want to put the result again or replace container with an empty one.

Putting all parts together we can define Option monad in scala in the following way

## Building new version of pipeline

Let’s return to our problem. First we need to reimplement parse

Argument and return type has been lifted respectively to the Option[String] and Option[Double] type. You can spot that I have used flatMap to have an access to the String value and based on the toDouble operation I returned some Double value or nothing - in case of parse exception. When an argument x is None the function passed to flatMap is not executed - so I am sure that String passed to monadic function is not null and I don’t have to make awkward null checks.

Next we need to take care of div

String arguments has been lifted to the Option[String] and return type is now Option[Double].

An x argument is passed to the parse and finally we have Double value in xx variable. If parse returns None then the whole function div is evaluated to None.

For y and z things works almost the same with one difference - we additionally requires that yy an zz must be none zero. This is expressed by calling flatMap with function zeroToNone. For 0 value zeroToNone returns an empty container None which causes that the whole expression parse(y).flatMap(zeroToNone) is evaluated to None what moves div function to return None.

Finally pipeline could look following

This pipeline generates

At the end we need only to filter out nones and get the value out of the Option

To do so there is a need to add 3 additional methods to Option

and to corresponding subclasses

Finally the pipeline

generates following stream of numbers

and this is all we need.