Functors, Monads, etc

in Scala

Vlad Patryshev

2017

​

http://tinyurl.com/functorsinscala

© 2020 Vlad Patryshev

Parameterized Type

type A[B]; type C[D,E]

trait F[G[_]]

class H[I,J[_],K]

//e.g.

new H[String, List[Double], Date]()

Functor: parameterized type with a map

trait F[X] {

def map[Y](f:X=>Y): F[Y]

}

// should a) preserve identity, b) preserve composition

map(f andThen g) == map(f) andThen map(g)

map(identity[X]) = identity[F[X]]

​

E.g. Set[X]

scala> val s = Set("a1", "a2", "a3")

s: scala.collection.immutable.Set[String] = Set(a1, a2, a3)

scala> val t = s.map(_ take 1)

t: scala.collection.immutable.Set[String] = Set(a)

​

Composition of two functors is a functor

F[G[X]].map(f:X=>Y) = ?

f: X => Y

G.map(f): G[X] => G[Y]

F.map(G.map(f)): F[G[X]] => F[G[Y]]

Not everything is a functor

E[X] = X => X

No way you can define map(f:X=>Y): E[X] => E[Y]

Covariance

trait F[+X]

// means that if X<:Y, then F[X]<:F[Y]

List[String] <: List[Object] <: List[AnyRef] <: List[Any]

// Does not work for Set[X]

Set[String] <: Set[Object]

But… (do you see the difference?!)

scala> val s = Set("a1", "a2", "a3")

scala> val u:Set[Any] = s map identity

u: Set[Any] = Set(a1, a2, a3)

scala> val v:Set[Any] = s

<console>:8: error: type mismatch;

found : scala.collection.immutable.Set[String]

required: Set[Any]

​

​

For Loop

for {

i <- List(2,3,5,7,11)

g <- List("hello", "goodbye")

} println(s"$g, $i")

For Loop Combinatorics

val seasonalGreetings: List[(String, Int)] =

for {

d <- List("christmas", "valentine", "4th of july", "thanksgiving")

g <- List("happy", "merry")

} yield (g, d)

// What happens here? We list all pairs. Equivalent to

val seasonalGreetings = list1 flatMap {d => {list2 map (g => (g,d)}}

Applicative Functor

• app: F[X=>Y] => F[X] => F[Y]
• // or, alternatively… /* X×Y is (X,Y) in Scala */
• andAlso[X,Y]: (F[X],F[Y]) => F[(X,Y)]

E.g. List(f,g) => List(1,2) => List(f(1),f(2),g(1),g(2))

Or (List(a,b), List(1,2)) => List((a,1),(a,2),(b,1),(b,2))

How about List of Lists?

val listOfLists:List[List[X]]

val flat: List[X] = for {

list <- listOfLists

elem <- list

} yield elem

Monad

• map(f:X=>Y): F[X] => F[Y]
• a functor F[X]
• flatten: F[F[X]] => F[X]
• unit: X => F[X]

E.g. List

List[List(1,2),List(3),List(),List(4,5,6)).flatten == List(1,2,3,4,5,6)

x => List(x)

val list: List[X]; list.map(_.toString)

map andThen flatten ⇒ flatMap

val allCells: List[Cell] = for {

person <- listAllPeople

cell <- person.listCells

} yield cell

​

val allCells = listAllPeople flatMap (_.listCells)

​

Monad Laws

If M[_] is a monad, then…

• unit: X => M[X]
• flatten[X]: M[M[X]] => M[X]
• unit(mx:M[X]).flatten = mx
• M[M[M[X]]].map(M[M[X]].flatten).flatten = M[M[M[X]]].flatten.flatten
• (and some more laws)

(e.g. List[List[List[A]]], can flatten two ways)

Examples

• List[X]
• Set[X]
• Option[X]
• Result[X]
• Future[X]
• Try[X]

​

Monad ≠ Container

def dice() = State[Random, Int](r => (r, r.nextInt(6) + 1))

def TwoDice() = for {

r1 <- dice()

r2 <- dice()

} yield (r1, r2)

// start with a known seed

TwoDice().eval(new Random(1L))

// resulting value is (Int, Int) = (4,5)

​

Composition of two monads? Oops...

F[G[F[G[X]]]] => F[G[X]]

will need G[F[Y]] => F[G[Y]]

List[Set[X]] => Set[List[X]] ?!

Option[List[X]] => List[Option[X]] ?!

List[Future[X]] => Future[List[X]] ?!

Strong Monad: Monad+Applicative

for {

(name,ssn) <- askName() andAlso askSsn()

company <- findCompany(companyName)

} yield new Employee(name, ssn, company)

Some monads are naturally applicative

for {

f <- listOfFunctions

x <- listOfValues

} yield f(x)

​

Summary

• Functors
• Variance
• Monads
• Applicatives

Thank you

Mille Grazie