Recursive Data Types

I was pointed in the direction of this lecture (and these slides). These are notes I made.

Imagine you want to build a hierarchy of professors and their students who too go on to be professors. You might like to model it like this:

case class ProfF[A](
  name: String,
  year: Int,
  students: List[A]
)

And have case classes to allow us to make recursive types because "type aliases can't be recursive but classes can" (using recursive type aliases result in "types [that] are infinite").

What's more, with ProfF "depending on how we wrap it we can represent just the pure data or the data annotated with database id" thus:

case class Prof(value: ProfF[Prof])

or

case class IdProf(id: Int, value: ProfF[IdProf])

But this is too tightly coupled with ProfF so let's refactor them like so:

case class Prof[F[_]](value: F[Prof])
case class IdProf[F[_]](id: Int, value: F[IdProf])

and too tightly coupled to the type of the id, so let's refactor that too:

case class Prof[F[_]](value: F[Prof[F]])

case class IdProf[F[_], A](id: A, value: F[IdProf[F, A]])

But there is nothing new under the sun as actually these useful data structures already exist in Scalaz.

case class Fix[F[_]](unfix: F[Fix[F]])
case class Cofree[F[_], A](head: A, tail: F[Cofree[F, A]])

and let's also throw in:

case class Free[F[_], A](resume: A \/ F[Free[F, A]])

Which is a type that says resume is either A or F[Free[F, A]]. It's like an Either is Scala. "\/[A, B] is isomorphic to scala.Either[A, B], but \/ is right-biased, so methods such as map and flatMap apply only in the context of the right case" (from here).

"In the same way you think of Cofree as a structure with labels at each node, Free is a structure with labels at the leaves". That is, where Cofree will always have an A, Free can either have an A but no further branches (ie, it's a leaf) or it has branches and no A (ie,  it's a branch to another Free).

Terminology

If F is a functor, Free is the free monad. 

Also, if F is a functor, Cofree is a comonad. More on this later.

"If we have a Fix we can always get an F out by calling unfix, and we can do that with Cofree by calling tail. The general name for this operation is project and data types that do this are called recursive types. And note that we can't do it with Free because you might not have an F; you might have an A. 

"But you can always go the other way. If you have the F you can construct a Free. Same with Fix. But you can't do this with Cofree because you also need an A. So this operation (the dual) is called embed and data types with this behavior are corecursive types."

This is used in the wonderfully named Matryoshka library.

What is it good for?

Well, we can build a recursive data structure to be sent to a persistence layer with this:

type Prof = Fix[ProfF]

and receive a similar (technically corecursive) data structure back but that now contains DB-assigned primary keys with this:

type IdProf = Cofree[ProfF, Int]

These are the basics you need to understand Doobie, a functional library for accessing JDBC.

First steps into Scalaz

Scalaz adds some nice features to Scala.

In the Haskell world, "functions are applicative functors. They allow us to operate on the eventual results of functions as if we already had their results" (from LYAHFGG).

(Where the "Functor typeclass, ... is basically for things that can be mapped over", "all applicatives are functors" [1] and applicatives have a function that has a type of f (a -> b) -> f a -> f b.)

So, why can't we map over functions in Scala? Well, now with Scalaz, we can!

import scalaz._
import Scalaz._

    val f: Int => Int = _ * 2
    val g: Int => Int = _ + 10

    val mapped = f.map(g)
    println(mapped(7))        // "24", ie (7 * 2) + 10

which is the same as saying f.andThen(g) and so the opposite of saying f.compose(g).

We can also flatMap over functions now and as a result can use for comprehensions:

    val addStuff: Int => Int = for {
      a <- f
      b <- g
    } yield (a + b)

    println("addStuff = " + addStuff(7)) // "31"

Why this monadic behaviour is so nice is that "the syntactic sugar of the for-comprehensions abstracts the details nicely enough for the user, who is completely oblivious of the underlying machinery of binding monads" (from here).

We can even raise a plain old Int to the level of monad with:

println(3.point[Id].map(_ + 1)) // prints out "4"

By using point, the "constructor is abstracted out... Scalaz likes the name point instead of pure, and it seems like it’s basically a constructor that takes value A and returns F[A]." (from Learning Scalaz).

[1] Functional Programming in Scala (Chiusano and Bjarnason)

Monads are easy too!

A lot of people are frightened of Monads for no reason. Perhaps it's because their origins are based in Category Theory. Or that they are used extensively in Haskell. But neither of these need to be understood for the average Java/Scala programmer.

All that needs to be understood are the Monadic Laws (from Coursera):

Monad Laws

Associativity

(m flatMap f) flatMap g == m flatMap (x => f(x) flatMap g)

Left unit

unit(x) flatMap f == f(x)

Right unit

m flatMap unit == m

(think of unit as just a factory function).

Note: f(x) will return a monadic structure, that is: f is of type X => M[X]  (if x is of type X and m is of type M in the above laws).

Like monoids, monads obey a few simple rules and that's that. So, what's so good about them?

Well, because monoids obey some laws, you can make assumptions about them (eg, when folding, you don't care if it's a left or right fold if you're using monoids).

With monads, you can make similar assumptions. For instance, given these simple functions:

  def addOne(x: Int)            : Int       = x + 1
  def times10(x: Int)           : Int       = x * 10

and this simple monad:

    val option7 = Some(7)

then these two lines are exactly equivalent:

    val outer = option7.flatMap(x => Some(times10(x))).flatMap(x => Some(addOne(x)))

    val inner = option7.flatMap(x => Some(times10(x)).flatMap(x => Some(addOne(x))))

This is useful when dealing with for-comprehensions (which are just syntactic sugar). 

Monads are also used a lot in Haskell as it's a lazy language and they make it actually do something (note: this is not my area of expertise).

The Monad API

Neither Scala nor Java 8 have a common trait or interface that all their monads implement even though they code. For instance, that's exactly what is done in Scalaz.

But, as mentioned, they're used in for-comprehensions in Scala so you might have been using them without even knowing! The compiler doesn't care that the monads don't have a common interface. It knows for-comprehension syntactic sugar can be converted to their respective map and flatMap methods. Then, using the monadic laws above, refactoring for-comprehensions is safe and easy.

Conclusion

So, what monads are is easy. Why they are useful is more subtle. Here is an interesting video on the subject of monads.

More on those Monoids

I mentioned in a previous post about Scalaz' implementation of Monoids. Having run through the code with somebody better at Scala than I am, here are my notes.

Our code imports the implicit means of creating a monoid. The signature of the method is this:

  implicit def optionMonoid[A: Semigroup]: Monoid[Option[A]] = new Monoid[Option[A]] {

The [A: Semigroup] looks a little like a type parameter but it is totally different. It's a Context Bound that "are typically used with the so-called type class pattern, a pattern of code that emulates the functionality provided by Haskell type classes, though in a more verbose manner" (from this excellent explanation).

Context Bounds of the form [X: Y] say: I am expecting an implicit value of type Y[X]. In fact, this line is equivalent to Scalaz' implementation:

    implicit def optionMonoid[A](implicit x: Semigroup[A]): Monoid[Option[A]] = new Monoid[Option[A]] {

Now, recall that my code using the Scalaz library looked like this:

    implicit val stringSemigroup: Semigroup[String] = Semigroup.instance[String]((x, y) => x + y)

    val mySemigroup: Semigroup[Option[String]] = Semigroup[Option[String]]

The first line is me just defining my Semigroup - nothing interesting there.

The second is much more magic. It invokes this Scalaz code:

object Semigroup {
  @inline def apply[F](implicit F: Semigroup[F]): Semigroup[F] = F

which is somewhat confusing as F is used for more than one purpose. Basically, this line says: there should implicitly be a value of type Semigroup[F] where F is defined in the call site and I will return that value. (Note that the symbol 'F' is confusingly used to represent both the returned value and the type at the call site).

Well, the only implicit value that we defined is our own stringSemigroup and that's of type Semigroup[String] not Semigroup[Option[String]]. But then we also imported Scalaz' optionMonoid that says if there is a Semigroup[String] hanging around in the implicit ether, I can deliver a Monoid[Option[String]]. Since Monoid is a type of Semigroup, mySemigroup is legitimately given this Monoid[Option[String]].

Et voila. Not immediately obvious to a Java programmer but that's how Scala does it.

Further reading

1. Stackoverflow: Scalaz learning resources.