Eli-Golin

11/21/2016 - 1:08 PM

CategoryTheory

```
A study of collections of concepts and arrows.
A 'concept' in our case is a type and an arrow is a morphism between concepts
(Somethind that converts one concept to another). In computer science a morphism
is a function defined against two types.
Category - grouping of concepts and arrows.
The most used category in programming is the category of types (classes traits
aliases and objects)
Category theory defines some low level concepts that if we manage to feet our
code into them, they become a design pattern.
Example: Designing a configuration library.
We would like to be able to construct a database connection,
based on configuration provided.
The purpose of this library is to be able to read configurations from different
locations. If any of this locations are updated the program should automatically
alter it's behavior the next item connection is requested.
trait Config[+A] {
def map[B](f:A => B): Config[B] //used to trsansform underlying configuration data
//If reading env variable of type string,
//I might want to make an integer out of this
def flatMap[B](f:A => Config[B]):Config[B]//Used to construct new config objects
//based on other config object
def get : A //Unsafe method for reading te configuration itself
//if this method is used you should know what to do in
//case of a failure.
}
object Config {
//We are assuming that map and flatMap are already implemented properly
def apply[A](data: => A) = new Config[A] {
def get = data
}
}
def environment(name:String):Config[Option[String]] = Config(
if(System.getenv.containsKey(name))
Some(System.getewnv.get(name))
else None
)
//No let's construct a db connection based on environment variable
def lift3[A,B,C,D](f:Function3[A,B,C,D]) = {
(oa:Option[A], ob:Option[B], oc:Option[C]) =>
for(a <- oa; b <- ob; c <- oc) yield f(a,b,c)
}
lift3(DriverManager.getConnection) //Returns a three argument function that
//works agains Option arguments
Using the DriverManager with the new Config library requires lifting the
getConnection function to take Config[Option[String]], rather than just Option[String]
Let's make a new 'lift' method instead that converts three argument method into
method that operate on config objects
def lift3Config[A,B,C,D](f:Function3[A,B,C,D]) = {
(ca:Config[A], cb: Config[B], cc:Config[C]) =>
for(a <- ca; b <- cb; c <- cc) yield f(a,b,c)
}
val databaseConnection = lift3Config(DriverManager.getConnection)(
Config.environment("jdbc_url"),
Config.environment("jdbc_user"),
Config.environment("jdbc_password")
)
Functors Monads and how they are related to categories:
Functors are transformations from one category to another that can also
preserve morphism.
Morphism - Changing one value to another in the same category.
Let's suppose we have a category of all possible types in Scala (Int,Long,Double..).
- Cat1
That means we have varios functions (morphisms) that can do the following
type A => type B (and we have a morphism between any two types)
The functor F is a 'type constructor' in Scala. For any type T in Cat1, we can
place that type in the 'type constructor' anf get a new type F[T] in new
category Cat2.
But obeying one rule, that for a function A => B in Cat1, there's a function
F[A] => F[B] in Cat2.
So if I have a function that converts String into Int, I must have a function that
converts F[String] to F[Int] - and this is exctly what 'map' function does.
Let's convert it into interface:
trait Functor[T[_]] {
def apply[A](x:A) :T[A] //That's the type constructor
def map[A,B](x:T[A])(f: A=>B) :T[B] //Given atransformed type T[A] and a morphism
// In the original category A => B, the
//value T[B] can be created
}
Functor implementation for Config:
object ConfigAsFunctor extends Functor[Config] {
def apply[A](x:A):Config[A] = Config(x)
def map[A,B](x:Config[A])(f:A => B) = x.map(f)
}
Endofunctor: Is a functor that converts concepts and morphisms in its category
back into the same category.
Example: If we have a category of cats, so an endofunctor would be a way to
convert cats and generic manipulation on cats, into a different type
of cats and different generic manipulations on them.
Monad are the means of combining a functor applications, if that functor is
an endofunctor.
So transforming a cat more than once by the same functor could be reduced into
a single functor application (flatten), similarly altering cat generic manipulations more
than once, can be reduced into a single alteration(flatMap).
In computer science monads are used to represen computations.
Definition:
trait Monad[T[_]] {
def flatten[A](m : T[T[A]]):T[A]
def flatMap[A,B](x:T[A])f(f: A => T[B])(implicit func:Functor[T]):T[B] = {
flatten(func.map(x,f))
}
}
In reality, a monad is the 'flatten' operation on functor. If we were to encode
the category theory directly into the Scala type system, the flatMap would require
an implicit Functor. For category theory applied to computer science, everything
is in the 'category of types'. The 'type constructor' functor F[_] applied to
a type T results in the type F[T], which is in the same category of types - so
it is an endofunctor.
A monad is the means of taking two such applications and reducing them to a
single - F[F[T]] becomes F[T] (we are combining functor applications)
Currying and applicative style:
Currying is the convertion of a function that takes multiple arguments into
a chain of functions that take a single argument.
A curried function accepts one of it's arguments and returns a function that
accepts the next argument. This chanin continues until the last function returns
a result.
In scala any function of multiple parameters can be curried.
'Applicative style' refers to using curried functions to drive the parameters
in applicative functors through them.
'Applicative functors' - Functors that support a method to convert mapped
morphisms into morphisms against mapped types.
Than means that if we have a list of functions, an applicative functor can create
a single function that accepts a list of argument values, and returns a new
list of results.
In Scala all functions (not methods) have 'curried' method that can be used
to convert from multiargument functions into curried functions.
val x = (x:Int, y:Double,z:String) => x + y + z
val y = x.curried //(Int) => (Double) => (String) => java.lang.String = <function1>
//y is a function that takes an Int and returns some other function
//that takes a Double and returns some other function that takes
//a String and returns a String
//The same as above
val y = (a: Int) => (b: Double) => (c: String) => x(a,b,c)
This trick workds when to promote a function of multiple simple parameters
to work with values inside Functor.
Let's become practical rgarding those monads,functors and applecatives:
If we have a type constructor C[_] and two types A and B, we would like to be
able to apply functions C[A] => C[B]
So;
1. Given a function A => B and a Functor, we can to do F[A] => C[B]
2. Given a function A => C[B] and a monad, we can do C[A] => C[B]
3. Given a C[A => B] and an applicative, we can do C[A] => C[B]
Examples:
//A container type
class MyBoxp[T](val value:T)
//Putting some value into the MyBox container
val boxedstring = new MyBox("Hello")
Now we would like to apply some transformations on the value inside the container
without leaving it. In other words we would like to apply C[A] => C[B]
Let's asume we would like to compute the length of the string in MyBox,
and get the result again in MyBox. So we a need a function of type
MyBox[String] => MyBox[Int]
def lengthOf (a:MyBox[String]):MyBox[Int] = ...
Since we already have a 'length' method on String type, we would like to make
some use of it:
def rawLengthOf(a:String):Int = a.length.
As we can see we need to transform it so let's write a transformation for it:
def map[A,B](rawFunc: A => B): MyBox[A] => MyBox[B] = (a:MyBox[A]) => new MyBox(rawFunc(a.value))
Let's summarize it all:
------------------------------
class MyBox[T](val value:T)
def map[A,B]( rawfunc:A=>B ) : MyBox[A]=>MyBox[B] = (a:MyBox[A]) => new MyBox( rawfunc(a.value) )
val boxedstring:MyBox[String] = new MyBox("Hello") // a boxed value
def rawLengthOf(a:String) : Int = a.length // the raw function we want to use
val transformedLenghtOf = map(rawLenghtOf) // applying the transformation, so we get our new function
val result:MyBox[Int] = transformedLengthOf( boxedstring ) // applying the new function
* We have MyBox[_] and we have a map function for MyBox - it is a Functor.
--------------------------------
Let's start with a function that takes a raw type and creates a boxed type
out of it:
def lengthOf(a:String) = new MyBox(a.length)
So now we need a new transformation
def flatMap[A,B](func: A => MyBox[B]): MyBox[A] => MyBox[B] = (a:MyBox[A]) =>
func(a.value)
The rest looks almost the same:
val transformedLengthOf = flatMap(lengthOf) //aplying the tranformation so we get or new function
val result:MyBox[Int] = tansformedLengthOf(boxedstring) //applying hte new function
* We have a MyBox[_] and we have a flatMap function fro MyBox - it is a Monad
---------------------------------
Now we start with our boxedstring, but now the 'rawLengthOf' boxed itself in a MyBox
val boxedLengthOf:MyBox[String => Int] = new MyBox(rawLengthOf _)
We need another converter for this case:
def apply[A,B](b:MyBox[A => B]):MyBox[A] => MyBox[B] = (a: MyBox[A]) => new MyBox(b.value(a.value))
val transformedLengthOf = apply(boxedLengthOf)
val result:MyBox[Int] = transformedLengthOf(boxedstring) //applying hte new function
* We have a MyBox[_] and an apply function - it is an applicative.
----------------------------------
Another perspective on the same concepts:
As we saw a Functor tansformation was implemented as a standalone function named 'map'
def map[A,B](rawFunc: A => B):MyBox[A] => MyBox[B] = {
(a:MyBox[A]) => new MyBox(rawfunc(a.value))
}
But a 'map' function taking a function is one possible representation, there's
another way to represent 'map'.
The above signature of 'map' is (A => B) => (MyBox[A] => MyBox[B])
The last parens can be left out:
(A => B) => MyBox[A] => MyBox[B] // This is exactly a signature of a curried function
// And it can be easily transformed back into multiple parameter list
((A => B),MyBox[A]) => MyBox[B]
Since the order of the parameters isn't important we can write it as:
(MyBox[A],(A => B)) => MyBox[B]
What in curried form is again:
MyBox[A] => (A => B) => MyBox[B]
So let's rewrite our 'map' function according to the above signature:
def map[A,B](a:MyBox[A]): (A => B) => MyBox[B] = {
(rawfunc: A => B) => new MyBox(rawfunc(a.value))
}
So far the class MyBox and the function map are only loosely related, i.e the
function map cold be easily located anywhere in our code base.
To orgenize it better and document the relationship of map with MyBox,
we could declare it as a method on the companion object:
object MyBox {
def map[A,B](a:MyBox[A]): (A => B) => MyBox[B] = (rawfunc: A => B) => new MyBox(rawfunc(a.value))
}
The object oriented presentation:
Having a function: (MyBox[A], (A =>B)) => MyBox[B] is a functional way of saying
the following:
class MyBox[A](val value:A) {
def map[A,B](rawfunc: A => B) = new MyBox(rawfunc(this.value))
}
So now we can do:
val n = new MyBox("Hellp")
n.map((a:String) => a.lenth).value
* Now the MyBox class can be used in 'for comprehension'
Another Scala-typical way to provide methods on objects although their class
does not implement them are wrapper classes and implicit conversion.
class MyBox[T](val value:T) {
override def toString() = s"MyBox($value)"
}
class MyBoxWrapper[T](w:MyBox[T]) {
def map[R](f: T => R):MyBox[R] = new MyBox(f(w.value))
def flatMap[R](f: T => MyBox[R]):MyBox[R] = map(f).value
}
object TestMonadWrapper extends App{
implicit def myBoxWrapper[S](mb:MyBox[S]) = new MyBoxWrapper[S](mb)
val ma = new MyBox("Hello World")
println(ma.map(a => a.length))
val res = for {
a <- ma
} yield a.length + 2
println(res)
val mb = new MyBox("Hola Mundo")
val res2 = for {
a <- ma
b <- mb
} yield a.size + b.zise
println(res2)
}
Monads as workflows:
A monadic workflow is a pipeline of computation that remains embedded inside the
monad. The monad can control the execution and behavior of he compuatation that's
nested inside it.
Monadic workflows are used to control side effects, control flow, and concurrency.
* Use monadic workflow for sequential computations.
* If parallelism needed we should use an applicative style
If sequencing needed use monadic style.
```