# Recursive Tail Call Optimization and Trampoline

Tail call optimization (or tail call elimination) allows recursive functions to re-use the stack frame instead of creating new frames on every call.

Thanks to that an author of recursive function in tail position is not constrained by the stack size. More over such a function runs faster than the function without optimization, because calling a function doesn’t create a new stack frame which is time and resource consuming operation.

The article can be found here

# Object Oriented Programming vs Functional Programming

Michael Feathers, the author of Working with Legacy Code, described in a neat way the difference between object and functional oriented programming:

OO makes code understandable by encapsulating moving parts. FP makes code understandable by minimizing moving parts.

More can be found here

In order to compile a given source code using static linking

there is a need to pass two additional flags to ghc like

• -optl-static
• -optl-pthread

then

# 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.

## Resources

Slides for Lunch2Learn (L2L) session are available here.

In functional programming monad is a design pattern which is used to express how states of computations are changing. It can take a form of some abstract data type constructor with two abstract functions.

In scala we can define this contract using Monad type class

Functions pure and flatMap for a given monad M[_] have to follow some laws - I will talk about them later.

Function map can be defined in terms of flatMap and pure and this is a bonus which we get for a free when we provide an instance of a Monad for a type M[_]. Moreover many useful functions can be defined in terms of flatMap and pure like map2, ap, filter and so on. This interface is so powerful then often is treated as a primitive one when goes to implement other functions.

We can think about M[A] like about some smart container for a value (values) of type A. This container abstracts away from how this value is kept. We can have many flavors of them like container:

• aware of whether or not the value exists
• with more then one value
• for which getting the value would trigger some kind of IO operation
• with value which eventually could appear in future
• with value or error
• with value dependent on some kind of state
• with value and some logging information
• etc

Monad let us focus on what we want to do with the contained value. Monad is like a context in which the value exists. When we want to do some computation we are abstracting over the context so we aren’t disrupted whether or not the value exists, we have many of them or the value may appear in a future. We want just to get the value out of the container for a moment to make some computation and then put it there again. The context is important only when we want to pull out a value permanently.

Another advantage of the monad is an ability of sequencing the computations. Having let’s say two computations we can very easily make dependence between them saying that the computations of the second depends on a result of the first. Of course this can be scaled to more than two.

At first glance, it may seem to be not so impressive because it is very common to make such things during coding. But be aware that monad frees us from thinking about the context in which the value exists. The context can be for example an asynchronous computation. Dealing with concurrency is challenging - we have to be very careful to not make a hard to spot mistakes. Monad takes care about this complexity, providing a result of the first computation as soon as possible giving us possibility to spawn another computation in asynchronous manner.

### Laws

• Left identity: return a >>= f ≡ f a
• Right identity: m >>= return ≡ m
• Associativity: (m >>= f) >>= g ≡ m >>= (\x -> f x >>= g)

These laws was taken from haskell because expressions there are very compact and easy to follow. Function >>= in scala maps to flatMap, return is just a pure, f x is an application of function f with x and the last one \x -> ... is a lambda expression.

Laws in scala can be written in a following way (using ScalaCheck)

If you are curious about implementation details take a look on this class

This section is a placeholder for a list of posts about monads mentioned in this article. I will try my best to deliver a missing content. Watch my blog for an update.

• Option
• Either
• Id
• Writer
• State
• Try
• IO
• List

# Monad Transformers - Part 2

In a previous post I introduced monad transformers and since now we should have a good feeling about their usage and how they can be helpful.

Designing a monad transformer we decided to fix inner most monad. This decision was dictated by the fact that we couldn’t replace code dependent on internal representation of that inner most monad. I think that this step could not be as obvious as I expected to be. And now I will try to make it more clear.

Let’s try to bite the problem from different side. Assume that we can write a monad transformer and know nothing about monads internal representation. Let’s call it CMonad (shorthand from ComposedMonad).

Such a class could look like

Here F[_] and G[_] are higher kinded type representing outer and inner most monad.

Then a problem introduced in a previous post could be solved following

Of course it doesn’t work because we haven’t yet provided implementation for flatMap and map

Let’s start with flatMap. To make things clear a little I introduced a new method flatMapF and defined flatMap in terms of flatMapF

In order to apply f : A => F[G[B]] we need to extract A from value: F[G[A]]

One attempt could end with following code

Now we can apply f with A and we will get fgb : F[G[B]]

In order to make compiler happy we need to take one step more - extract G[B] from F[G[B]] and return that value from inner most flatMap. This of course is not possible knowing only that F and G form a monad.

Another attempt can lead us to the code like

And now we need to extract F[G[B]] from G[F[G[B]]]. This also is not possible if we know nothing about internal representation of G.

# Monad Transformers - a Quick Recap

Someone have said that monads are like burrito, if you ever taste one than you can’t imagine live without it.

Monads are a powerful tool. Thanks to them we can abstract over computation. We can make one computation depended on another and if needed fail fast.

But one day the time will come when we have two different monads and we will find out that they don’t compose !

Let’s make some code to visualize the problem. I am going to show two use cases and I will start with the simplest one.

### Case 1

We have two entities : User and Address and two functions retrieving data with the respect of a given predicate

Our goal is to write a function which for a given login returns user’s street name

So far so good - quite simple and classic enterprise task :)

However there are two caveats to this solution worth noting. What happened if there is no such user or the user exists but it has no address ? It is obvious that we will see Null Pointer Exception - sick !

Of course we can filter out those nulls and rewrite functions to be aware of them but as you already know this is also not a good solution. Can we do better ? Yes we can, let’s introduce a context aware of whether value exists or not (Option data type).

But wait below function is not compiling…

It turns out that Future and Option monads do not compose in such a way. For a first look, composition looks very natural in for comprehension, but if we transform it into series of flatMap and map at the end, we will notice that the puzzles don’t feet. If we start with Future than the function passed to flatMap must return a Future. In our case we want to return Option in the middle and based on it return a next Future being a container fo an user’s possible address.

Equipped with this knowledge we can rewrite our function in the following way

Now it compiles and return correct results. But it is not as readable as our first naive attempt. Can we do better ? Ideally we would want to have something like

We need somehow to fuse Future with Option in a smart way to make the composition possible.

#### Fusing Future with Option

We already know that for comprehension deals with flatMap, map, withFilter and foreach. In our case compiler needs only flaMap and map to de sugar for. So let’s introduce a new data type OptionFuture, which wraps Future[Option[A]] and in a proper way handles flatMap in order to compose Future with Option.

Take a little time to better look at OptionFuture data type. First question coming to my mind is - can we make it more abstract ? It turns out that we can abstract over Future very easly. In terms of Future we are calling only two kinds of functions:

• flatMap
• Future.successful

It means that Future can be swapped with Monad.

What about the Option ? Over the Option we are performing pattern matching - so it means that we need to know something about it structure.

And because of that we can’t to abstract over it.

This leads us to the definition of monad transformer for Option and we call it OptionT

#### Monad transformer for Option

OptionT[F[_], A] abstracts over F and A and it only requires that F is a monad. The name of the monad transformer comes from the fact that, in order to implement this wrapper, we need to know what the inner most monad in the stack is - in this case Option. Without this knowledge we can’t compose any two given monads with itself.

A minimal api for monad can be described by following trait

And its instance for Future you can find below.

#### A solution

Putting all pieces together we can finally write

of course we can return directly Future[Option[String]] just by calling value function on the result like

` and that’s it.

#### Final word

At the beginning I said that I have two cases to show, but because the post could be to long to go through without a brake I decided to split it into two pieces. The whole code base used in this post can be found in the following link

More in part 2

# Gentle Introduction to Functional Programming - Live Coding Session

Slides for Lunch2Learn (L2L) session are available here.

# Recursion - a Quick Introduction

Slides for Lunch2Learn (L2L) session are available here.