Monoids, Functors, and Other Dark Horses of Functional Programming

in Scala (mostly)

Titus Stone


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.


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


Part 1:

Algebraic Data Types and Algebraic Structures

What is a Type?

Statically Typed Languages

Dynamically Typed Languages

1.) A strategy for memory allocation


Boolean: 1 bit

2.) A template of associated behavior and data


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

3.) A way to interact with something


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?


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

  • Operations
  • Rules


Operation: Addition

Rule: Distributive Property

a + b == b + a


// 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


// 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


Given a and b, return a appended to b

Rule: Associative property

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


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


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


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>...


In other words...

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

When would we ever use this?

Every day


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:


Recall what we're talking about:

Describing a set of types through operations and rules


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.


"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;
} = 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 =

// s2.type == Seq[String]

Array is a Functor

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

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

Option is a Functor

val o: Option[Int] = Some(10)
val o2 =

// o2.type == Option[String]

Future is a Functor

val f: Future[PoiLike] = PlaceService.getPlace(1234)
val f2 =

// f2.type == Future[Int]

Promises are "mostly" Functors

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

Promise.pipe ==

Part 3:

Using Functors

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


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


val o: Option[String] = Some("hello")

// Some("HELLO")

val o2: Option[String] = None

// None

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

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

val cityAndState = { city => { state =>
    city + ", " + state

Q: What is the type of cityAndState?

A: Option[Option[String]]

val cityAndState = { city => { state =>
    city + ", " + state


val cs1 = { city => { state =>
    city + ", " + state
val cs2 = cs1.flatten

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


flatMap is a shortcut for map+map+flatten

val cs1 = address.locality.flatMap { city => { 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


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

These are equivalent:

o1.flatMap { a =>
  o2.flatMap { b => { 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


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) { place =>

Q: What is the return type of { place=> Ok( ...?

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?



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


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

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 =

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) =

  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]) =

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

What did we gain?

Our functionality is now available on anything that implements Monoid

def cityName(city: LocalityLike) = 
    .when( == "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]) = 
    .when( == "US") { fs.fromString(city.region) }

Which means we can do...

// Or
// Or event