Functional Composition With Monads, Kleislis and Functors
I’ve been learning Scala for my current client project and I find writing to be a great tool to test my understanding of any given topic. This means there might be a few Scala posts coming up soon as I keep learning interesting things.
Today I’ll be exploring a few different ways in which you can compose programs. I’ll be using Scalaz in this post.
The examples that follow all deal with Vehicles - more specifically makes and parts:
1 2 3 4 5
Next we have a couple of functions which interact with these case classes:
1 2 3 4 5
So we have a function from
Make and then a function from
List[Part]. From set theory we know this implies we must have a function from
List[Part]. This is nothing more than simple function composition:
1 2 3 4 5 6 7 8
Pretty boring stuff.
A more realistic example accounts for failure in our functions. One way we can encode this is using the
Option data type:
1 2 3 4
Now we have a function
make: Int => Option[Make] and a function
parts: Make => Option[NonEmptyList[Part]]. Based on our first example we should have a way to create a function from
Option[NonEmptyList[Part]]. This isn’t immediately obvious however.
make does return a
Make, it is wrapped inside an
Option so we need to account for a possible failure. This leads to our first attempt:
1 2 3 4 5 6
While this works, we had to manually create the plumbing between the two functions. You can imagine that with different return and input types, this plubming would have to be rewritten over and over.
All the function
f above is doing is serving as an adapter for
parts. It turns out there is a couple of ways in which this pattern can be generalised.
Option is a monad so we can define f using a for comprehension:
1 2 3 4 5
Which is simply syntactic sugar for:
1 2 3 4 5 6 7 8 9
The reason this is better is that
parts could operate under a different monad but the client code would not need to change. In the example below, we’re operating under the
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
We used the exact same for comprehension syntax to compose these operations. This works because both
List are monads.
Notwithstanding, this still feels like unnecessary plumbing. All we are doing with the for comprehenstion /
flatMap is extracting the values from their respective monads to simply put them back in. It would be nice if we could simply do something like
make compose parts as we did in our first example.
By creating a Kleisli arrow from a function, we are given a function that knows how to extract the value from a Monad
F and feed it into the underlying function, much like bind does, but without actually having to do any binding yourself.
To use a concrete example, let’s create a kleisli arrow from our
You can read this type as being a function which knows how to get a value of type
Make from the
Option monad and will ultimately return an
Option[NonEmptyList[Part]]. Now you might be asking, why would we want to wrap our functions in a kleisli arrow?
By doing so, you have access to a number of useful functions defined in the Kleisli trait, one of which is
<==< (aliased as
1 2 3 4
This gives us the same result as the version using the for comprehension but with less work and with code that looks similar to simple function composition.
Not there yet
One thing that was bugging me is the return type for
Sure this works but since lists already represent non-deterministic results, one can make the point that the Option type there is reduntant since, for this example, we can treat both
None and the empty List as the absence of result. Let’s update the code:
1 2 3 4 5 6
It seems we’re in worse shape now! As before,
parts’s input type doesn’t line up with
make’s return type. Not only that, they aren’t even in the same monad anymore!
This clearly breaks our previous approach using a kleisli arrow to perform the composition. On the other hand it makes room for another approach: Functor lifting.
Say you have a function
A => B and you have a functor
F[A]. Lifting is the name of the operation that transforms the function
A => B into a function of type
F[A] => F[B].
This sounds useful. Here are our function types again:
We can’t get a function
Int => List[Part] because
make returns an
Option[Make] meaning it can fail. We need to propagate this possibility in the composition. We can however lift
parts into the
Option monad, effectively changing its type from
Make => List[Part] to
Option[Make] => Option[List[Part]]:
1 2 3
f now has the type
Int => Option[List[Part]] and we have once again successfully composed both functions without writing any plumbing code ourselves.
Mark pointed out to me that
lift is pretty much the same as
map but with the arguments reversed. So the example above can be more succintly expressed as:
1 2 3
If you are only now getting to this whole Functor/Monad/Kleisli thing this was probably quite heavy to get through. The point I am trying to make here is that learning at least some of the abstractions provided by Scalaz is certainly worthwhile. They encode common patterns which we would otherwise keep re-writing a lot of the time.
Special Thanks to Mark Hibberd who kindly reviewed an early draft of this post.