Study note of the Monad concept in Scala. It is based onthe book: Functional Programming, Simplified (FPS). As suggested by the author, one has to understand the state monad to really understand the monad concept. It helps to implement a lazy IO monad using the state monad concepts. Monad transformer is the last piece of the puzzle.
1 The IO Monad in the FPS book and in Cats Effect
The main conculsion is that Scala doesn’t define Monad, it uses types that define map andflatMap methods thus they can be used in a for-compreshension.
The IO monad has two benefits: as an unsafe marker and using in for expression. It is defined as the following:
|
|
The author defined it using an early evaluation, whenever flatMap or map is called, the IO operation passed in the constrctor is executed, as shown in bind(run) – the by-name argument is called first and its result is passed as an input to the bind function. The result of bind is executed again.
The cats effect implementation separates the composition and execution.
|
|
The IO functions are executed when program.unsafeRunSync() is executed.
2 The State Monad
A state monad has three parts: a state monad, a concrete state and its application. Following is a demo implementation of a state monad.
|
|
First, the StateMonad is a case class that has one constructor parameter: run: S => (S, A) where S is the state type and A is a computed value. It is a function that takes an initial state and creates a new state and a new result. An instance of the StateMonad defines how state changes and how result is calculated. Multiple instances define a sequence of changes. To compose these changes, we define two typical monad methods: flatMap and map.
The flatMap method is the essential method that defines the composition behavior. It is important to konw that this method simple create a StateMonad instance from the function parameter, nothing else is executed. The logic of this newly created monad is defined by its run constructor argument. The run method first executes the run method of the current monad instance to create a new state and a new value, then use the new value and the flatMap function parameter to create a new monad instance. The function parameter could be one of two value: if it is the last step, the function is one generated from the map method and it is done by running the changed state and the map function result. Otherwise, it is the result of the flatMap method of the next monad instance, then it runs the new instance’s run method.
In the simplest case, there is only one monad instance and the map method is called. Only two actons are performed: the monad instance calls its run method, then map the value. The result is the changed state and the mapped value. The demo code is as the following:
|
|
If there are mutiple steps, all intermediate steps in a for expression just creates a new monad instance whose run logic has three steps:
- execute the
runto generate a new state and new value. - call the next expression in
for, actully it just create a new monad instance by calling the next monad’sflatMap. - call the
runmethod of the newly created monad with new state. The newly created monad links to its next monad instance in the prevsiousflatMapcall.
The demo code is as the following:
|
|
The benefits of the state monad are
- on need to pass the state around, the states are passed inside
flatMapandmap. - composition by
forexperession is simple. - the plan and execution are separated thus multiple plans can be composed and reused.
The composition of multiple plans is as the following:
|
|
The cons are more code setup and not easy to understand.
3 A Lazy IO Monad
Based on the state code, the following is an implementation of a lazy IO Monad.
|
|
Following are implementation details:
- A case class cannot have a by-name parameter, therefore, the monad is defined as a regular class with a
runmethod to access the by-name constructor parameter. The companion object defines theapplymethod to create a new instance. - The
flatMapjust create a monad instance. The instance’s constructor parameter is defined to run the current instance’s constructor parameter, generate a new monad instance and then run the new instance’s code. No IO functions areexecuted until therunfield of the Monad is accessed. - Wrap the
printlnandreadLininto the IO Monad.
4 Monad Transfomers
A monad transformer can stack its own effects on another monad. Not all monads have monad transfomers. To define a monad transfomer StateT, we need to define a Monad trait that can be extended by other monads to be stacked. The implementation of a monad deterimine the existence of a monad transfomer. For example, it is easy to change the state monad as a monad transformer, but it is impossible to make a strict IO monad a monad transfomer.
First, there is a forumal defination of Monad as the following:
|
|
The F[_] is a type constrctuor representing a type once it is constructed with a type parameter, for example, an IO monad. An implementation of Monad[F] needs to implement lift and flatMap.
The source code of a state monad transformer is as the following:
|
|
The StateT has a state of type S and the result of a state change is of a type of A. For a type F[_] to be used, there must be an implicit value of M of type Monad[F]. The value is used to implement the four methods of StateT: flatMap calls M.flatMap() to chain the actions, point calls M.lift() to covnert a value of A to StateT type. The map() method is implemented via flatMap and pioint. The lift method calls M.map to lift a F[_] value to a StateT. Simply, the StateT uses an implicit Monad[F] to drive the execution.
There are two possible types of functions: the StateT methods and F[_] methods. StateT methods returns StateT and can be used in for expression directly. However, you need the above lift method to convert F[_] method results to a StateT value.
To use the above monad transformer, you need to define a F[_] and an implicit Monad[F]. The folowing is an example for the IO operations:
|
|
The following is an applicatoin of the StateT and MyIO constructs:
|
|