Friday, 22 June 2012

Scala: Comonad (scalaz example)

When we were talking on Functor - we described it as a construction that can apply function to incapsulated value and return a new instance of the same container with function result value inside. Quite useful construction, it is even implemented by scala library's classes: like Option, List and others. To be honest Scala's standart library classes mixing Functor and Monad, but lets do not concentrate on this now.


Some cases require value to be extracted from container, or wrap it it into container (Functor for example), to allow container to be be proceed as business value as well, I know this is not clean, let's rephrase it. Sometimes we need a construction CM[A] and want to extract A. This is called Copure. Oposite case is convertion CM[A] to CM[CM[A]] , this is called Cojoin. Mixing previous two with Functor gives a birth to Comonad.
Class diagram from the scalaz library is bellow:
As we can see Comonad is mixing Functor, Copure and Cojoin. I feel this is too abstract, even example  absents makes it another one forgotten construction. Actually pure Comonad entities aren't frequently met in standart Scala libraries.
In scalaz Comonad's ad-hoc implementations are defined for Tuple, NonEmtyList, MapEntry, Tree and few others.


Lets look into NonEmptyList. From the name it's crear - it implements List that is guaranteed to be nonempty (there isn't Nil in the head of the List). As it was mentioned there is ad-hoc Comonad implementation for NonEmptyList. This means that Cojoin, Copure and Functor are defined as well. Copure implementations is reutrning the head of the list, which is guaranteed to be non empty:
and Cojoin returns all tails from the list All tails Example:

Example 1: apply 

We already covered that Cojoin returns CM[CM[A]], in our case it is the NEL of NELs, where each element is a tail. Imagine situation when we want to measure the weight (sum of int elements) of each tail. How to get the list of the tail list from NEL we already know: cojoin, that returns NEL[NEL[Int]], it's natural to reduce the Int list into String sum representation via folding right operation, for each tail this should be a function NEL[Int]=>String. We remember that Comonad is Functor in meantime, then we can map reduce function to each element with help of map method (fmap in scalaz). Signature is fmap:(NEL[NEL[Int]], NEL[Int] => String) => NEL[String]. Putting all together: Method apply is implementing Cokleisli map, and it is already in scalaz lib. Here is wrapper around our apply method:

Example 2: Composition 

Additionally cokleisli class from the scalaz is using Comonad nature for copmosing two functions. Imagine situation: there are two functions
f: CM [A] =>  B
g: CM [B] => C
Where B and C aren't compatible and CM is Comonad. Tasks is composing of f and g. As we mentioned Comonad is implementing these methods:

    map: (A => B) => W[A] => W[B]
    copure: W[A] => A
    cojoin: W[A] => W[W[A]]

Mapping f to input returns CM[CM[A]] => CM[B], looks like this is what we need for composing to g. Let's adopt our input: CM[A] can be cojoined and become a CM[CM[A]]. Final composition function is Cokleisli composition:
    r(x) = g(
as you can guess that r(x) is already defined in sclaz as Cokleisli.=>=. Imagine that we want to count the sum from the list of sums for all tails. And then determine is it enough to represent the value as a String via 1 symbol (here I mean is it less than 10). There are 
function that maps all tails to the sum of elements;
function that reduces previous function results to final sum and comparing to 10 (first double digit number). 
Actually we are simulating very generic behaviour for MapReduce approach. Here is possible implementation:
According to Formula:
r(x) = g(
It will work as:
   g(NonEmptyList(1, 0, 3, 0) =
= g( NonEmptyList(NonEmptyList(1, 0, 3, 0), NonEmptyList(0, 3, 0), NonEmptyList(3, 0), NonEmptyList(0)).map(f)) =
= g(NonEmptyList(4, 3, 3, 0)) =
= false
As you can see Comonad can be used in very interested way, example above is looking very similarly to MapReduce construction (of course it is not the same). In meantime Monad is just a Functor that knows how to extract incapsulated value, or present it as a Container of Containers (Comonads of course), when both operations are meanfull in business - it helps to dispatch you data in sexy way).

No comments:

Post a Comment