Thursday, February 23, 2012

Can I Read with my Monad ?

Hello again.

 Last time we talked about the state Monad and we how solved this problem using type lambda. 
I am sorry to say I did it again, following a strange path. During one of my morning fitness session I have been watching Rúnar Bjarnason presentation about Scalaz functional programming in Scala. As I am progressively understanding new concepts in Scala, I can now start getting interested in a small selection of libraries. 
In my humble opinion, this is the way things should work: before using any dependency, one should get sure he understands (more than) the basic bricks of theory and potential applications at the origin of the creation of the library. 
Getting my hands into Functors, Monads, Applicative Functors and their application can now open the door to a (small) range of selected libraries (not frameworks of course). Scalaz comes as a natural selection to be used... soon. 

Naturally, before I have to understand a little bit more. Rambling in search of a concept implementation, derived from the talk, I realized I never took the time to write a Monad "concept" - in the concept pattern parlance - targeting functions. 
Approaching functions as Functors, Monads and Applicative Functors demands a lot of effort to a lot of people (including me). But I would not say that creating the Monad implementation for function gets as harder as working with State Monads, I have to come back to on a regular base. And guess what, my understanding progresses each time. 
The starting question we should ask - from my point of view - is : if we assume a Monad to manage a context for embedded values, what kind of context a function can be ? Looking at the type of a function, one can consider the returned result as the embedded value extracted from a context being the input value. Then, what would a map function on a such a context look like:



In school we learnt very early a way to manage this kind of mapping between functions, thanks to function composition:



In the final version I just took benefit from the contravariance in the type definition of the applied transforming function f. An alternate version could be:



So far, so good. 
From the previous posts, and while playing with our project located here, we agreed on the following definitions for both Monads and Functors:



With a simple map implementation for Functors, and having provided a generic flatMap definition, the only implementations we should worry about are both the apply and flatten method:



The easiest one, the apply function, embeds an input value in a function context. This fresh context should be able to restore the value any time. A sort of constant function. 

Regarding the flatten method, typically what we expect is to flatten a function producing a function ((A) ⇒ (A) ⇒ T seen as (A) ⇒ ((A) ⇒ T)) to a function producing a simple value. That is exactly the purpose of the new function we created, applying successively the possible input x value to each of the function argument. 

Armed with our implementations we now can derive a full Applicative Functor implementation. As for the State Monad pattern, the Applicative Functor implementation accepts a single type parameter  Applicative[M[_]].
The type of functions we are working with are double parameter type constructor . In our working context, the type of returned values is the the embedded type in our Monad definitions. The function input parameter type defines a context from within the embedded type is extracted, therefore we must freeze the input type somehow. This is when type lambda comes into the place:



We freeze the function input type A while the type lambda projection (through #) allows us to set a single parameter container to our Applicative Functor definition. But what's the use ? The Learn You a Haskell canonical example remains very simple:



We basically defines two operations accepting an input parameter each, and return the result of the combined functions. The more interesting part being that each function reads from the same input source. I guess that's why we call the pattern the "Reader" Monad.

How many times did we encounter this situation when we had to apply different operations onto an input context from which we aimed to extract, then process values ? 
The most recent example that came to my mind was setting up an environment from accessible configuration information. In his book, Joshua Suereth explains how to produce then combine optional Config instances while building an application. Starting from there and using our new pattern just see how we can simulate the whole scenario:




In our scenario we build some environment using connection, datastore, and application configuration. The configuration (aka Config case class) is a container manageable using an implicit Applicative Functor.

the configBuilder method implements a complete environment setup process. We use our Reader Monad implementation in order to extract from a unique source
  • a connection configuration
  • a datastore configuration from the connection configuration
  • application configuration
Then we build a complete environment using from single source of properties (a Map here). The environment is set using the sugar syntax we defined around Applicative functors in a previous post.


Now, we know how to separate the concern of what we create from a single source from how to process it. Although the example remains simplistic, we have in our every day life as programmers, opportunities to clutter the code while applying different processes to  a same immutable input (input analysis, input validation, information display etc.). The Reader Monad can save the day gathering in the same comprehension the whole process.

Code can be found here.

That's all folks. Not a big one this time. I need to do some Clojure too.

Be seeing you !!! :)

Wednesday, February 15, 2012

Variation on the State Monad in Scala

Houdy,

a brief one this evening, but I need to communicate. A friend of mine who recently read the post on the state Monad pattern asked me why I did not extend the generic Monad trait I was working on. 
Astute question. It took me some time to get an answer and provide him with a compiled version reproducing the canonical stack sample. I come today with a version, that, I submit to your judgement in need of feedbacks. As a reminder my previous proposal for both a Monad and a Functor trait lead me to:


No big deal. When I came to define the state Monad I bumped into a wall because of the expected behavior of the defintion of state Monad (from what I learnt for Learn You a Haskell). Roughly quoting the book, a stateful computation may be viewed as function taking as input some state and returning a value paired with some new state:


No matter how I took the problem I was facing two impediments
  • neither Function1[S, (A, S)] nor (S) => (A,S) are type constructors
  • Whatever would be the solution, I would have to work with a single argument type constructor  M[_]  while implementing Monad[M]
The first problem , I solved it mimicking Haskell creating a State class :


having at my hand a type constructor...alas with two type arguments. 

 The deal then was to freeze somehow one of the parameters in order to propose to the Monad trait to implement a single type parameter: from State[_, _] to M[_]
The method defintions in the generic Functor and Monad traits already fix the type parameter constraint as the type of the Monad returned value (in Haskell parlance). So obviously my Monad trait would have to be parameterized (<- neologism :)) with some kind of State[_, S] thing. 

Wait a minute. The idea would be to define my single argument type constructor under the scope of my state Monad definition, supposedly having "already" bound the State type (there is blur notion of "already" for me). It seems that the solution lays onto the use of a type lambda. As in the referenced article I have to "curry" somehow my double argument State[_,_] type constructor: 


The expression ({type λ[α] = State[α,S]}) seems to me like an anonymous structural type, the type I want being State[α,S]. The type S is "already" (still blur) bound to the State Monad implementation. We use then a type projection (aka #) in order to specify explicitly the λ type we expect as the single argument constructor. Roughly said, a type projection allows to refer to the  inner type in a type. All this is new for me and any pointer in addition to Joshua Suereth book will be welcome. 
All we need is a Kestrel combinator (look here and there for detailed explanation):


in order to use our State Monad in a for comprehension:


The complete code project can be found here.

The  implementation is naive and this field of Scala ramblings is new. Do not hesitate to feedback or to give pointers. 

Be seeing you !!! :)

Tuesday, February 7, 2012

Applicative ramblings in Scala

Hello again.

I was looking (a am still looking) for a good way to present the result of my ramblings on applicative functors without hurting the feelings of people who would like to start a Scala journey. 
As a "young" Scala explorer I would like to tell them, that I really started understanding the full potential of Scala while starting to deal with category theory concepts and typing concepts. 

Reading Learn you a haskell (LYAH) is a good start and trying to reproduce some of the example from Haskell to Scala is a nice move. I only started reading my first book on conceptual mathematics after reading LYAH and it is helping. David Greco told me recently that patterns like Monads, Functors, Applicative Functors etc. could be viewed as a kind of mathematically proven patterns. I stick to his point of view, claiming in addition that these are mathematically proven programming patterns (in opposition to architectural patterns). 
As so, learning these mathematical concepts represents a big part of our programming job. Nevertheless, I also claim that it is possible, if not recommended, to adopt both the mathematical understanding approach and the practical approach. 
We foresaw in previous posts that monads can be seen as contexts, allowing to safely manipulate their content with higher level functions with the help of functors:


trait Functor[M[_]] {
  def map[T, U](source: M[T])(f: T => U): M[U];
}

trait Monad[M[_]] {

  def apply[T](data: T): M[T]

  def flatten[T](m: M[M[T]]): M[T]

  def flatMap [T, U](source: M[T])(t: T => M[U])(implicit f: Functor[M]): M[U] = {
    flatten(f.map(source)(t))
  }
}

where M[_] is the type constructor of the container assumed as a Monadic container. Paired with the following implicit definitions located in a package.scala file,

 
  implicit def ToFunctor[F[_] : Functor, A](ma: F[A]) = new {
    val functor = implicitly[Functor[F]]
    final def map[B](f: A => B): F[B] = functor.map(ma)(f)
  }

  implicit def ToMonad[M[_]: Functor : Monad, T](source: M[T]) = new {
    val monad = implicitly[Monad[M]]
    def flatMap[U](f: T => M[U]): M[U] = monad.flatMap(source)(f)
  }

our Monadic definitions can make us taking benefit from the for comprehensions in scala. Having created a Writer to log traces during operations, logging a simple operation became:

def logNumber(x: Int): StringWriter[Int] = StringWriter[Int](x, "Got number " + x + " ")
val value = for {
      a <- logNumber(3)
      b <- logNumber(5)
    } yield a * b

      logNumber(3).flatMap(x =>
        logNumber(5).map(y =>
          x * y))

where the log operation - as a side effect - has been cleanly separated from the operation per se. I have slightly modified my definitions after reading again Joshua Suereth book and some enlightning discussion with David. I adopted a definition of Monads parameterized with the container type only.
(Another rule: when like me you are learning an try to pull your level up, try to find skilled people. There is no shame in not understanding or knowing, even at 40. There is shame only in living in the comfort zone). 
The project source is located here

To Joshua: if I have the chance you read the post some day, thanks for the book (please don't beat me for the part of codes I have stolen in my small project :)) 

Until now, we made no progress in understanding Applicative Functors ! I know. Considering our monad definition, a base frustration comes from the fact that we can only map a single argument function:

final def map[B](f: A => B): F[B] = functor.map(ma)(f)

In essence, what we would like to be able to, is to manipulate a bunch of values embedded in structures like our Monads. It would be really interesting to work at a higher order level allowing us to manipulate our Monadic values with our simple functions in a very expressive (aka self explanatory) way, like in Haskell:

ghci>(+) <$> (Just 2) <*> (Just 3)
Just 5

Here a simple (+) operation is applied to two possible values producing a possible values. With an impossible value argument, this would become:

ghci>(+) <$> (Just 2) <*> Nothing
Nothing

so an impossible value. 

In one line, thanks to this "Applicative style", we apply an operation on two possible operands, pulling off the values from their context and pushing the new value in an identical context.

Why the Applicative name: these functions a rpovided by the scala typeclass definition:

class (Functor f) => Applicative f where  
    pure :: a -> f a  
    (<*>) :: f (a -> b) -> f a -> f b  

(<$>) :: (Functor f) => (a -> b) -> f a -> f b  
f <$> x = fmap f x  

In addition we have the benefit of managing the possible non existence of a one of the operands. 

Can we do that in Scala ? We can. We are going to produce something like:

def add = (a: Int, b: Int) => a + b

add :@: List(1, 2) :*: List(3, 4)

where :@: stands for <$> and :*: for <*>. 

Almost...because both :@: and :*: express the same intent but mostly as "sugar" combining more elementary functions 

The idea is simply to "lift" the applied function into the world of our container and to use function currying

Like explained in the link and in J. Suereth book, we can view currying as splitting a function taking multiple input arguments into a function that takes a single argument and return a function that takes a single arguments and so on...:

scala> val f = (a: Int, b: Int, c: Int) => b * b - 4 * a * c
f: (Int, Int, Int) => Int = <function3>

scala> val c = f.curried
c: Int => Int => Int => Int = >function1>

scala> c(1)
res3: Int => Int => Int = >function1>

In the previous Haskell example, the <$> function lift the (+) function into the world of Maybe Monads and partially applies it to (Just 2), then, apply the embedded partially applied function to (Just 3) via the <*> function (do not confuse with partial functions in Scala) 

The following trait intends to lift up functions and apply lifted functions to "Applicative", assimilated to Monad and Functors:


trait Applicative[F[_]] {
  self: Functor[F] with Monad[F] =>

  def pure[T](data: T) = apply[T](data: T)

  def applyA[T, U](fs: F[T => U])(source: F[T]): F[U] = {
    implicit val f: Functor[F] = self

    flatMap(source) {
      x: T => map(fs)(f => f(x))
    }
  }

  def mapA[T, U](t: T => U, source: F[T]): F[U] = {
    applyA(pure(t))(source)
  }
}

  • Lifting is realized through the invocation of the pure function.
  • applyA extracts the function(s) embedded in the F[_] fs context, the values x embedded in the F[_] source context and produces a M[_] result containing the output of f(x).
  • mapA lifts up an input function

What about the currying operation ? As Scala exposes 23 traits abstracting functions taking up to 22 parameters we should take into account all the possibilities. Let us consider two of them:


  def liftA2[T, P, Q, A[_]](f: (T, P) => Q, a1: A[T], a2: A[P])(implicit applicative: Applicative[A]): A[Q] = {
    import applicative._
    applyA(mapA(f.curried, a1))(a2)
  }

  def liftA3[T, P, Q, R, A[_]](f: (T, P, Q) => R, a1: A[T], a2: A[P], a3:A[Q])(implicit applicative: Applicative[A]): A[R] = {
    import applicative._
    applyA(applyA(mapA(f.curried, a1))(a2))(a3)
  }

Basically the function liftA2 takes a method with two parameters, two Monadic instances, then producing a Monadic result after applying the function to the embedded values in the Monadic instances. 
Scala allows for the currying of the f function using the application of the curried method on the function instance. 
This is where the method mapA gracefully lift up the curried function instance and applies it once to the a1 argument producing a partially applied function
We can then apply applyA on the resulting partially applied function and a2, producing the final result.

Same for liftA3 and so on for hypothetical liftA4,5,6 etc. 

Wait a minute: applyA(mapA(f.curried, a1))(a2) does not offer any "Applicative style"  sugar. I struggled a lot with the sugar syntax and reading again chapter 11 of Joshua book provided me with the path to the solution:

case class BuilderToApplicative[T1, A[_]](m1: A[T1])(implicit applicative: Applicative[A]) {
def :@:[T2](f: T1 => T2): A[T2] = applicative.mapA(f, m1)

    def :*:[T2](m2: A[T2]) = BuilderToApplicative2[T2](m2)

    case class BuilderToApplicative2[T2](m2: A[T2]) {
      def :@:[T3](f: (T1, T2) => T3) = Applicative.liftA2(f, m1, m2)

      def :*:[T3](m3: A[T3]) = BuilderToApplicative3[T3](m3)

      case class BuilderToApplicative3[T3](m3: A[T3]) {
        def :@:[T4](f: (T1, T2, T3) => T4): A[T4] = Applicative.liftA3(f, m1, m2, m3)
      }
    }
  }

  implicit def toApplicative[T, A[_]](m: A[T])(implicit applicative: Applicative[A]) =
    new BuilderToApplicative[T, A](m)

This solution is almost identical to Joshua version of its config builder. 
My first version was incomplete as I was expecting a simple BuilderToApplicative class to handle the :@: and :*: function application with a liftA2 method (Sometime you hate yourself ;)). 
A better understanding of Joshua's book proved me that his builder was the right answer, creating a building environment with same number of levels as the possible maximum number of arguments in a Scala functions. We provide here the two first level. No doubt I will provide the others when needed

In each BuilderToApplicativeX class we apply a liftAX method (Joshua if we ever meet some day I owe your a capuccino, a tea, etc. whatever you want). 

 Why not applying that to lists. Defining an ad-hoc binding between lists and Applicative trait:

implicit object ApplicativeList extends Applicative[List] with Monad[List] with Functor[List]{
override def map[T, U](source: List[T])(f: (T) => U) = source.map(f)

  override def apply[T](from: T) = List(from)

  override def flatten[T](m: List[List[T]]) = m.flatten
}

we try:

def add = (a: Int, b: Int) => a + b
def addd = (a: Int, b: Int, c: Int) => a + b + c

def basics() {
  println(liftA2(add, List(1, 2), List(3, 4)))
  println(liftA3(addd, List(1, 2), List(3, 4), List(5, 6)))
  println(add :@: List(1, 2) :*: List(3, 4))
  println(addd :@: List(1, 2) :*: List(3, 4) :*: List(5, 6))
}

providing :

scala> import com.promindis.user._
import com.promindis.user._

scala> import UseApplicativeFunctor._
import UseApplicativeFunctor._

scala> basics()
List(4, 5, 5, 6)
List(9, 10, 10, 11, 10, 11, 11, 12)
List(4, 5, 5, 6)
List(9, 10, 10, 11, 10, 11, 11, 12)

Notice that these one liners easily replace for comprehensions expressions, leading to clearer syntax. 

Why all that stuff? My initial intent was to reproduce a kind of sequence function like in Haskell. The sequence function provides from a list of Monadic values a Monadic list a values and I found (still find) that priceless:

def sequence[T, A[_]](input: List[A[T]])(implicit applicative: Applicative[A]): A[List[T]] = {
import applicative._
  input match {
    case (x :: xs) =>
      def cons(head: T, list: List[T]): List[T] = head :: list
      liftA2(cons, x, sequence(xs))
    case _ => pure(List.empty[T])
  }
}
So List[A[T]] produces A[List[T]]. Taking Joshua's example of producing connection data from identifiers:
  def getConnection(input: List[Option[String]]) = {
      def doSomething(fromParameters: List[String]) =  fromParameters.toString()

      for {
        withParams <- input.sequenceA
      } yield doSomething(withParams)
  }

we get

scala> getConnection(List(Some("url"), Some("user"), Some("passwd")))
res5: Option[String] = Some(List(url, user, passwd))

scala> getConnection(List(Some("url"), None, Some("passwd")))
res6: Option[String] = None

only by applying the sequence method to the list using the implicit definition:

  implicit def toSequenceable[T, A[_]](list: List[A[T]])(implicit applicative: Applicative[A]) = new {
    def sequenceA = Applicative.sequence(list)
  }

We provide ad-hoc meaning to our list of Option's, returning a valuable answer only when all the elements are provided. No NullPointerException, no catch, no if. Just fluent language. A more useful example? Taking a class a workers, executable in pool, and provided a naive Applicative definition for Future traits:

case class W(value: Int) extends Callable[Int] {
def call() = {
    Thread.sleep(3000)
    value
  }
}

object Futures {
  implicit object ApplicativeFuture extends Applicative[Future] with Monad[Future] with Functor[Future] {
    def apply[T](data: T) = new Future[T] {
      override def get() = data

      override def get(timeout: Long, unit: TimeUnit) = get()

      override def cancel(mayInterruptIfRunning: Boolean) = false

      override def isCancelled = false

      override def isDone = true
    }

    def flatten[T](m: Future[Future[T]]) = m.get()

    def map[T, U](source: Future[T])(f: (T) => U) = new Future[U] {
      override def get() = f(source.get())

      override def get(timeout: Long, unit: TimeUnit) = f(source.get(timeout, unit))

      override def cancel(mayInterruptIfRunning: Boolean) = false

      override def isCancelled = false

      override def isDone = true
    }
  }

I can now transform a list of Futures into a Future of a list of the expected values:

 def exec(workers: W*)(implicit pool: ExecutorService): List[Int] = {
    workers.toList.map {pool.submit(_)}.sequenceA.get()
  }


  def futures() {
    implicit val pool = Executors.newCachedThreadPool()

    val start = System.currentTimeMillis

    val result = add :@: exec(W(1), W(2), W(3)) :*: exec(W(4), W(5), W(6))

    val ellapsed = System.currentTimeMillis - start
    println("Got " + result + " in " + ellapsed + " ms")

    pool.shutdown()
  }

For a more real-world example, check the Akka application
 The code presented here is vailable there. That's all folks. See you (very) soon with my last ramblings in the Disruptor world in Scala.

 Be seeing you !!!:)