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 !!!:)

1 comments:

missingfaktor said...

Great post. Very nicely explained. Keep 'em coming. :)

Post a Comment