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