Monoids, Functors, and Other Dark Horses of Functional Programming

in Scala (mostly)

Titus Stone

Functor

A functor is a type of mapping between categories. Functors can be thought of as homomorphisms between categories [where] a homomorphism is a structure-preserving map between two algebraic structures.

Wikipedia

Functional programming combines the flexibility and power of abstract mathematics with the intuitive clarity of abstract mathematics.

XKCD

Part 1:

Algebraic Data Types and Algebraic Structures

What is a Type?

Statically Typed Languages

Dynamically Typed Languages

1.) A strategy for memory allocation

Primitives

Boolean: 1 bit

2.) A template of associated behavior and data

Classes

class Foo {
  val name: String = "foo"
  def print = println(s"I am $name")
}

3.) A way to interact with something

Interfaces

trait Vendor {
  val ids: Set[Int]
  val name: String
}

The point:

When we say "type", we actually are talking about a lot of concepts not just String's and Int's

Q: Is it possible to have types of types

(which in a very meta way are themselves types)

int, long, double, float

aka "Numeric"

How would we go about describing "Numeric"?

How do we describe a type of types?

A:

All of the types which can do X operations where those operations follow Y rules

---

• Operations
• Rules

Example

Operation: Addition

Rule: Distributive Property

a + b == b + a

Example

// Type of types
trait Numeric[A] {
  // Operation:
  def add(x: A, y: A): A
}

// Rule:
numeric.add(5, 1) mustEqual numeric.add(1, 5)

Q: What makes a type Numeric?

A: Any type A, where A is able to be added
such that x + y == y + x

Implementation

// Valid
val Int = new Numeric[Int] {
  def add(x: Int, y: Int) = x + y
}

val Double = new Numeric[Double] {
  def add(x: Double, y: Double) = x + y
}

// Not Valid
val String = new Numeric[String] {
  def add(x: String, y: String) = x + y
}

Numeric is a way to categorize type:

Types where this is true

It has defined defining a set of types (int, long, double, float)

Why is this valuable?

Another Example

Append

Given a and b, return a appended to b

Rule: Associative property

(a Append b) Append c == a Append (b Append c)

Identity

Return the default/empty/zero value for the type

Rule: Identity Append a == a Append Identity == a

trait Example[A] {
  def append(x: A, y: A): A
  def identity: A
}

Monoid

trait Monoid[A] {
  def mappend(x: A, y: A): A
  def mzero: A
}

Implementations

val String = new Monoid[String] {
  def mappend(x: String, y: String) = x.append(y)
  def mzero = ""
}

val Int = new Monoid[Int] {
  def mappend(x: Int, y: Int) = x + y
  def mzero = 0
}

Algebraic Structure

An algebraic structure generally refers to a set<1> with one or more finitary operations<2> defined on it [where] a finitary operation is an operation that takes a finite number of input values<3> to produce an output<4>...

Wikipedia

In other words...

trait Foo[A]<1> {
  def op<2>(arg: A<3>): A<4>
}

When would we ever use this?

Every day

Array

We typically think of an array (Seq) as a type -- which it is -- but it's really a type of types, an algebraic structure

Array is describing a set: all types which adhere to the interface exposed by Seq

It just happens to be the set of types Array is describing is every type, including itself

Questions about algebraic data types and monoids?

Part 2:

Functors

Recall what we're talking about:

Describing a set of types through operations and rules

Functor

A functor is a type of mapping between categories. Functors can be thought of as homomorphisms between categories [where] a homomorphism is a structure-preserving map between two algebraic structures.

Wikipedia

"a map between two algebraic structures"

trait Functor[A] {
  def map(f: A => B): Functor[B]
}

1.) Given a function that takes A and returns B

2.) Return a new Functor of type B

trait Functor[A] {
  def map(f: A => B<1>): Functor[B]<2>
}

Functors in Javascript

var Foo = function(value) {
  this.value = value;
}

Foo.prototype.map = function(f) { // where f is A => B
  return new Foo(f(value));
};

Seq is a Functor

val s: Seq[Int] = Seq(1, 2, 3)
val s2 = s.map(_.toString)

// s2.type == Seq[String]

Array is a Functor

var s = [1, 2, 3];
var s2 = s.map(function(x) { return x.toString(); });

// ["1", "2", "3"]

Option is a Functor

val o: Option[Int] = Some(10)
val o2 = o.map(_.toString)

// o2.type == Option[String]

Future is a Functor

val f: Future[PoiLike] = PlaceService.getPlace(1234)
val f2 = s.map(_.mqId)

// f2.type == Future[Int]

Promises are "mostly" Functors

var p = $.get("/api/place/1234");
var p2 = p.pipe(function(json) {
  return json.name;
});

Promise.pipe == Functor.map

Part 3:

Using Functors

fmap always returns a new Functor of B, however the behavior of when fmap "applies" can varry.

Option

sealed trait Option[A] extends Functor[A]

case class Some[A](protected val value: A) extends Option[A] {
  val map(f: A => B) = Some(f(value))
}

case object None[A] extends Option[A] {
  val map(f: A => B) = this
}

Option

val o: Option[String] = Some("hello")
o.map(_.toUpperCase)

// Some("HELLO")

val o2: Option[String] = None
o2.map(_.toUpperCase)

// None

What happens when we get a Functor[Functor[A]]?

trait AddressLike(
  country: String,
  region: Option[String] = None,
  locality: Option[String] = None,
  ...
)

val cityAndState = address.locality.map { city =>
  address.region.map { state =>
    city + ", " + state
  }
}

Q: What is the type of cityAndState?

A: Option[Option[String]]

val cityAndState = address.locality.map { city =>
  address.region.map { state =>
    city + ", " + state
  }
}

flatten

val cs1 = address.locality.map { city =>
  address.region.map { state =>
    city + ", " + state
  }
}
val cs2 = cs1.flatten

// cs1.type == Option[Option[String]]
// cs2.type == Option[String]

flatMap*

flatMap is a shortcut for map+map+flatten

val cs1 = address.locality.flatMap { city =>
  address.region.map { state =>
    city + ", " + state
  }
}
// cs1.type == Option[String]

A: Option[Option[String]]

* = flatMap is technically part of a Monad which itself is a Functor

for/yield is another way of writing chained flatMap's

Given

val o1 = Some("a")
val o2 = Some("b")
val o3 = Some("c")

These are equivalent:

o1.flatMap { a =>
  o2.flatMap { b =>
    o3.map { c =>
      a + b + c
    }
  }
}

for {
  a <- o1
  b <- o2
  c <- o3
} yield a + b + c

flatten and flatMap are available on all Functors in Scala

Future

map applies the given function f returning not the result of f, but a new Future such that when the value eventually resolves, f will be applied to it

class PlaceController extends Controller {
  def place(id: String) = Action.async {
    val futurePlace: Future[PlaceLike] = PlaceService.getPlace(id)
    futurePlace.map { place =>
      Ok(views.html.place(place))
    }
  }
}

Q: What is the return type of
futurePlace.map { place=> Ok(views.html.place(place) ...?

A: Future[Html]

So what is onSuccess and onFailure?

class Future[U] {
  def onSuccess[U](pf: PartialFunction[T, U]): Unit
  def onFailure[U](pf: PartialFunction[T, U]): Unit
}

The return type is the giveaway, Unit

onSuccess and onFailure mutate the Future, providing it a partial function that will be called when the future resolves.

They do not return a new Future.
They are not Functor-like.

If map only applies to when the future succeeds, how do we get back a new Functor when it fails?

recover

RecentlyViewedController

def get: Action[AnyContent] = Action.async { request =>
  val p = Promise[SimpleResult]()
  val f = fetchUserState(request.cookies)
  f map {
    ...
  }

  f onFailure {
    case e => Logger error("Recently viewed: " + e.getMessage)
  }

  f recover {
    case _ => p success Ok
  }

  p future
}

RecentlyViewedController

def get: Action[AnyContent] = Action.async { request =>
  fetchUserState(request.cookies)
    .map { ... }
    .recover { case e =>
      Logger.error("Recently viewed: " + e.getMessage)
      Ok
    }
}

Questions about using functors?

Part 4:

Designing With Functors

Always calling .getOrElse on Option's is stupid

Solution: Use a monoid to get the identity value in cases of None

implicit object StringMonoid extends Monoid[String] {
  def mappend(x: String, y: String) = x + y
  def mzero = ""
}

implicit def safeValue[A](opt: Option[A])(implicit md: Monoid[A]): A =
  opt.getOrElse(md.mzero)


val some: Option[String] = Some("asdf")
val none: Option[String] = None

println(some.toUpperCase + none.toUpperCase)
> "ASDF"

Another Problem: Optionally add things to a Seq based on a conditional.

This is ugly...

val s = Seq.empty
if (cond1) s = s ++ Seq(value1) else s
if (cond2) s = s ++ Seq(value1) else s
if (cond3) s = s ++ Seq(value1) else s

We could use an implicit class...

implicit class SeqOps[A](s: Seq[A]) {
  def when(cond: => Boolean)(value: A) =
    if(cond) s ++ Seq(value) else s

  def unless(cond: => Boolean)(value: A) =
    when(!cond)(value)

  def always(value: A) = when(true)(value)
}

This would allow...

val widgets = Seq.empty
  .unless(place.isInstanceOf[BizlocHotel]) { BookingWidget(...) }
  .when(place.isInstanceOf[PoiLike])       { CategoryWidget(...) }
  .when(place.isInstanceOf[AirportLike])   { DelaysWidget(...) }
  .always                                  { RecentlyViewedWidget(...) }

There is a Monoid in there

s ++ Seq(value) is really Monoid Append

Seq.empty is really Monoid Identity

Let's apply our logic to a value that has a Monoid

implicit class MonoidOps[A](origin: A) {
  def when(cond: => Boolean)(value: A)(implicit md: Monoid[A]) =
    if(cond) md.mappend(origin, value) else origin

  def unless(cond: => Boolean)(value: A)(implicit md: Monoid[A]) =
    when(!cond)(value)

  def always(value: A)(implicit md: Monoid[A]) =
    when(true)(value)
}

What did we gain?

Our functionality is now available on anything that implements Monoid

def cityName(city: LocalityLike) = 
  city.locality
    .when(city.country == "US") { city.region }

We could take this really far and make a conversion from String

trait FromString[A] {
  def fromString(value: String): A
}

And how things are off the hook

def cityName[A](city: LocalityLike)(implicit md: Monoid[A], fs: FromString[A]) = 
  md.mzero
    .always(fs.fromString(city.locality))
    .when(city.country == "US") { fs.fromString(city.region) }

Which means we can do...

cityName[String](place)
// Or
cityName[Html](place)
// Or event
cityName[Seq[String]](place)