Learning Scalaz from learning Scalaz

May 31, 2015

These are my notes from working through learning Scalaz with Scala Study Group.

sbt

The code in these notes uses Scalaz 7.1.0, which is available via sbt:

build.sbt:

scalaVersion := "2.11.2"

val scalazVersion = "7.1.0"

libraryDependencies ++= Seq(
  "org.scalaz" %% "scalaz-core" % scalazVersion,
  "org.scalaz" %% "scalaz-effect" % scalazVersion,
  "org.scalaz" %% "scalaz-typelevel" % scalazVersion,
  "org.scalaz" %% "scalaz-scalacheck-binding" % scalazVersion % "test"
)

scalacOptions += "-feature"

Day 0

We begin day 0 with an introduction of some of the basics that will be built on later, and a preview of some interesting things to come.

Polymorphism

Further reading

Sum function

Monoid

This is interesting:

def sum[A](xs: List[A])(implicit m: Monoid[A]): A =
  xs.foldLeft(m.mzero)(m.mappend)

It doesn't convert instances of A to any "enriched" type. It just provides functions (vs. methods) that operate on instances of A. See the note in FoldLeft/Method Injection below.

It's also synonymous with a "context-bound" type parameter:

def sum[A: Monoid](xs: List[A]): A = {
  val m = implicitly[Monoid[A]]
  xs.foldLeft(m.mzero)(m.mappend)
}

FoldLeft

Method injection

Day 1

In day 1, we look at some basic type classes. Let's implement them for our own data type, Amount:

sealed trait Amount
case object One extends Amount
case object Couple extends Amount
case object Few extends Amount

val one: Amount = One
val couple: Amount = Couple
val few: Amount = Few

Equal

implicit val equal: Equal[Amount] =
  new Equal[Amount] {
    def equal(a: Amount, b: Amount): Boolean = a == b
  }
assert(few === few)
assert(couple =/= few)

Order

implicit val order: Order[Amount] =
  new Order[Amount] {
    def order(a: Amount, b: Amount): Ordering =
      (a, b) match {
        case (One, One)       => Ordering.EQ
        case (Couple, Couple) => Ordering.EQ
        case (Few, Few)       => Ordering.EQ
        case (_, One)         => Ordering.GT
        case (Few, _)         => Ordering.GT
        case (One, _)         => Ordering.LT
        case (_, Few)         => Ordering.LT
      }
  }
assert(one lt couple)
assert(few eq few)

Show

implicit val show: Show[Amount] =
  new Show[Amount] {
    override def shows(a: Amount): String = a.toString
  }
assert(couple.show === "Couple")

Read

Scalaz doesn't include a Read type class, but let's make one anyway.

trait Read[A] {
  def read(a: String): Option[A]
}

implicit val read: Read[Amount] =
  new Read[Amount] {
    def read(a: String): Option[Amount] =
      a match {
        case "One"    => Some(One)
        case "Couple" => Some(Couple)
        case "Few"    => Some(Few)
        case _        => None
      }
  }
assert(implicitly[Read[Amount]].read("Couple") === Some(Couple))

Enum

implicit val enum: Enum[Amount] =
  new Enum[Amount] {
    def pred(a: Amount): Amount =
      a match {
        case One    => Few
        case Couple => One
        case Few    => Couple
      }
    def succ(a: Amount): Amount =
      a match {
        case One    => Couple
        case Couple => Few
        case Few    => One
      }
    def order(a: Amount, b: Amount): Ordering =
      Amount.order.order(a, b)
  }
assert(few.succ === one)
assert((one |-> few) === List(one, couple, few))

Truthy

Eugene goes on to implement a rather confusing set of type classes to use for JavaScript-like truthiness. Let's see if we can simplify it a bit.

trait Truthy[A] {
  def truthy(x: A): Boolean
}

object Truthy {

  def apply[A](f: A => Boolean): Truthy[A] =
    new Truthy[A] {
      def truthy(a: A) = f(a)
    }

  implicit val intTruthy: Truthy[Int] = Truthy({ x => x != 0})

  implicit def listTruthy[A]: Truthy[List[A]] = Truthy({ x => !x.isEmpty })

  def truthy[A: Truthy](a: A): Boolean =
    implicitly[Truthy[A]].truthy(a)

  def truthyIf[A: Truthy, B, C](cond: A)(ifyes: => B)(ifno: => C) =
    if (implicitly[Truthy[A]].truthy(cond)) ifyes else ifno

  implicit class TruthyOps[A: Truthy](a: A) {
    def truthy: Boolean = implicitly[Truthy[A]].truthy(a)
  }

}
import Truthy.truthy
import Truthy.truthyIf
import Truthy.TruthyOps

assert(truthy(1))
assert(!truthy(Nil: List[Nothing]))
assert(truthyIf(1)("yes")("no") == "yes")

assert(1.truthy)

We have to cast Nil as a list, because listTruthy is invariant in A, so it requires a value of type "list of something", but Nil has the explicit type Nil.

This alludes to an interesting consequence of FP in Scala: since sum types are implemented as case objects or case classes that extend a sealed trait, they rely on inheritance. This means that each data constructor is also its own type, distinguishable from the sum type itself.

Type class fever

There seem to be two distinct ways to do type classes in Scala: either through implicit values, or implicit conversions. These can be combined to take advantage of teach other, but it gets tricky.

Implicit values

Imagine that we want to introduce a new type class, Add:

trait Add[A] {
  def add(a: A, b: A): A
}

def add[A: Add](a: A, b: A): A =
  implicitly[Add[A]].add(a, b)

An Add implementation for Int simply adds two integers:

implicit val intAdd: Add[Int] =
  new Add[Int] {
    def add(a: Int, b: Int): Int = a + b
  }
assert(add(37, 5) === 42)

Type classes as implicit values have a functional flavor: there's only one instance of a given type class implementation (i.e. a static Add[Int] that handles addition for all integers). It has no state, and is essentially a static singleton function.

Implicit conversions

Imagine that instead of add(37, 5), we want fancy infix syntax so that we can write 37 add 5. We'll need to introduce an implicit conversion:

implicit class AddInt(a: Int) {
  def add(b: Int): Int = a + b
}
assert((37 add 5) === 42)

This is fine, but it's redundant -- we've implemented the logic for add in two places: intAdd#add and AddInt#add.

We can avoid this duplication and generalize our implicit conversion for any type by relying on the corresponding implicit value:

implicit class AddOp[A: Add](a: A) {
  def add(b: A): A = implicitly[Add[A]].add(a, b)
}
assert((37 add 5) === 42)

Day 2

Functor

The implicit coversions method of implementing type class instances that we saw on day 1 is referred to here as injected operators.

The Functor type class abstracts over type constructors, rather than the simple type variables that we saw before:

trait Functor[F[_]] { self => ...
trait FunctorOps[F[_],A] extends Ops[F[A]] { ...

To implement Functor for our Amount type, we'll need to parameterize it, so that it becomes an amount of something:

sealed trait Amount[A]
case class One[A](a: A) extends Amount[A]
case class Couple[A](a: A, b: A) extends Amount[A]
case class Few[A](a: A, b: A, c: A) extends Amount[A]

Now we can implement Functor[Amount]:

implicit val functor: Functor[Amount] =
  new Functor[Amount] {
    def map[A, B](fa: Amount[A])(f: A => B): Amount[B] =
      fa match {
        case One(a) => One(f(a))
        case Couple(a, b) => Couple(f(a), f(b))
        case Few(a, b, c) => Few(f(a), f(b), f(c))
      }
  }
assert(((One(6): Amount[Int]) map { x: Int => x * 7 }) === One(42))

Phew, Scala needed a lot of help with that line.

Function as Functors

This gives us a way, map, to compose functions in the reverse order from compose. Scalaz aliases map as .

val inc = (x: Int) => x + 1
val timesTwo = (x: Int) => x * 2
assert((inc ∘ timesTwo)(3) === 8)
assert((timesTwo ∘ inc)(3) === 7)

The order of arguments is different between Haskell's fmap and Scalaz's map:

fmap :: (a -> b) -> f a -> f b
final def map[B](f: A => B): F[B] = F.map(self)(f)

My guess is this is, among other reasons, to make type inference work with fewer manual type annotations.

We can use our Functor's built-in lift method to convert a function of type A => B into a function of type Amount[A] => Amount[B]:

val amountTimesTwo = Functor[Amount].lift(timesTwo)
assert(amountTimesTwo(Few(1,2,3)) === Few(2,4,6))

There are many other functions available: >|, as, fpair, strengthL, strengthR, and void.

Applicative

Apply

You can think of <*> as a sort of a beefed-up fmap. Whereas fmap takes a function and a functor and applies the function inside the functor value, <*> takes a functor that has a function in it and another functor and extracts that function from the first functor and then maps it over the second one.

This looks bizarre for Amount, but it works:

implicit val applicative: Applicative[Amount] =
  new Applicative[Amount] {
    def point[A](a: => A): Amount[A] = One(a)
    def ap[A, B](fa: => Amount[A])(f: => Amount[A => B]): Amount[B] =
      fa match {
        case One(a) =>
          f match {
            case One(g) => One(g(a))
            case Couple(g, _) => One(g(a))
            case Few(g, _, _) => One(g(a))
          }
        case Couple(a, b) =>
          f match {
            case One(g) => Couple(g(a), g(b))
            case Couple(g, _) => Couple(g(a), g(b))
            case Few(g, _, _) => Couple(g(a), g(b))
          }
        case Few(a, b, c) =>
          f match {
            case One(g) => Few(g(a), g(b), g(c))
            case Couple(g, _) => Few(g(a), g(b), g(c))
            case Few(g, h, i) => Few(g(a), h(b), i(c))
          }
      }
  }
assert((One(21): Amount[Int]) <*> One({ x: Int => x * 2 }) === One(42))

In addition to <*>, Apply gives us <* and *>:

assert((One(6): Amount[Int]) <* One(7) === One(6))
assert((One(6): Amount[Int]) *> One(7) === One(7))

Option as Apply

Applicative Style

^(f1, f2) { ... } vs |@|

assert(^((One(6): Amount[Int]), One(7)) { _ * _ } === One(42))
assert(((One(6): Amount[Int]) |@| One(7)) { _ * _ } === One(42))

Lists as Apply

Zip Lists

Useful functions for Applicatives

Apply[F].lift2
sequenceA :: (Applicative f) => [f a] -> f [a]
def sequenceA[F[_]: Applicative, A](list: List[F[A]]): F[List[A]]
def sequenceA[F[_]: Applicative, A](list: List[F[A]]): F[List[A]] = list match {
  case Nil     => (Nil: List[A]).point[F]
  case x :: xs => (x |@| sequenceA(xs)) {_ :: _}
}
assert(sequenceA[Amount, Int](List(One(2), One(3), One(7))) === One(List(2,3,7)))

Day 3

Kinds and some type-foo

Types are little labels that values carry so that we can reason about the values. But types have their own little labels, called kinds. A kind is more or less the type of a type. … What are kinds and what are they good for? Well, let’s examine the kind of a type by using the :k command in GHCI.

-- Learn You a Haskell for Great Good!

Scala 2.11 includes the :k (or :kind) REPL command, which lets us inspect the kind of a type:

scala> :k -v Either
scala.util.Either's kind is F[+A1,+A2]
* -(+)-> * -(+)-> *
This is a type constructor: a 1st-order-kinded type.

The kind * is read "type". It is analogous to the value 1. In Scala, it is written as the type variable A.

The kind * -> * is a type-level function that, given a type, yields a type. It is a first-order-kinded type. Examples: Option, List, etc.

Why are * -> * and * -> * -> * both considered to be first-order-kinded types?

The kind (* -> *) -> * should probably be called a higher-kinded type constructor (like higher-order functions), but they're not. In Scala this might be X[F[A]].

Scala (thanks to SIP-18) calls first-order kinded types higher-kinded types.

Tagged type

Tagged types are a way to simulate Haskell's newtype, with wich we wrap an existing type in something to present it as another type.

type Tagged[U] = { type Tag = U }
type @@[T, U] = T with Tagged[U]

This avoids the cumbersome boxing and unboxing we typically have to do for things like:

case class KiloGram(value: Double)

Because @@ is a type constructor of two type parameters, Scala lets us use it with infix notation:

A @@ KiloGram // same as @@[A, KiloGram]

Here's one I did in 2012:

// The setup

type Tagged[U] = { type Tag = U }
type @@[T, U] = T with Tagged[U]

class Tagger[U] {  def apply[T](t : T) : T @@ U = t.asInstanceOf[T @@ U] }
def tag[U] = new Tagger[U]

trait Named
trait Person extends Named

type Name = String @@ Named
def name(name: String): Name = tag(name)

trait Registry {
  def getPerson(name: Name): Option[Person]
}

// Now to test it

case class Dude() extends Person

object InMemRegistry extends Registry {
  private val people: Map[Name, Person] = Seq((name("Joe") -> new Dude())).toMap
  def getPerson(name: Name) = people.get(name)
}

val bob = name("Bob")
val joe = name("Joe")

InMemRegistry.getPerson(bob) // returns None
InMemRegistry.getPerson(joe) // returns Some(Dude())

References

About those Monoids

Here we're leading up to associativity and the identity value.

Monoid

trait Monoid[A] extends Semigroup[A] { self =>
  def zero: A
}

A monoid is also a semigroup.

Semigroup

trait Semigroup[A] { self =>
  def append(a1: A, a2: => A): A
}

It's operators:

trait SemigroupOps[A] extends Ops[A] {
  final def |+|(other: => A): A = A.append(self, other)
  final def mappend(other: => A): A = A.append(self, other)
  final def ⊹(other: => A): A = A.append(self, other)
}

The type class + operators plurality is finally starting to feel natural.

Note that mappend does not apply appending -- it means putting two things together to get a similarly-shaped new thing, in the monoidal way.

Back to Monoid

Haskell's mempty is Scalaz's zero.

Tags.Multiplication

Scalaz has built-in tags (of tagged types fame) in Tags.

scala> Tags.Multiplication(10) |+| Monoid[Int @@ Tags.Multiplication].zero
res21: scalaz.@@[Int,scalaz.Tags.Multiplication] = 10

But they're not always needed:

scala> 10 |+| Monoid[Int].zero
res22: Int = 10

Tags.Disjunction and Tags.Conjunction`

These are tagged types for booleans, representing || and &&.

scala> Tags.Disjunction(true) |+| Tags.Disjunction(false)
res28: scalaz.@@[Boolean,scalaz.Tags.Disjunction] = true

Ordering as Monoid

My head asploded at this point.

Day 4

Functor Laws

From HaskellWiki/Functor:

All instances of Functor should obey:

fmap id      = id
fmap (p . q) = (fmap p) . (fmap q)

Functor Laws

The Functor laws, identity and associativity, can't be validated at compile time in Scala.

Scalaz includes the FunctorLaw trait which, coupled with ScalaCheck, lets us test the validity of our functor implementations.

$ sbt
> test:console
scala> functor.laws[List].check
+ functor.invariantFunctor.identity: OK, passed 100 tests.
+ functor.invariantFunctor.composite: OK, passed 100 tests.
+ functor.identity: OK, passed 100 tests.
+ functor.composite: OK, passed 100 tests.

To use this on our Amount functor, we need to create a random Amount generator, and an Arbitrary instance for it:

val gen: Gen[Amount[Int]]=
  for {
    x <- Arbitrary.arbitrary[Int]
    y <- Arbitrary.arbitrary[Int]
    z <- Arbitrary.arbitrary[Int]
    a <- Gen.oneOf(One(x), Couple(x,y), Few(x,y,z))
  } yield a

implicit val arbitrary: Arbitrary[Amount[Int]] =
  Arbitrary(gen)
$ sbt
> test:console
scala> functor.laws[Amount].check
+ functor.invariantFunctor.identity: OK, passed 100 tests.
+ functor.invariantFunctor.composite: OK, passed 100 tests.
+ functor.identity: OK, passed 100 tests.
+ functor.composite: OK, passed 100 tests.

Breaking the law

We can break our functor by adding a line to the pattern match:

case One(a: Int) => One(f.asInstanceOf[Int => B](42))

Pow!

$ sbt
> test:console
scala> functor.laws[Amount].check
! functor.invariantFunctor.identity: Falsified after 0 passed tests.
> ARG_0: One(0)
+ functor.invariantFunctor.composite: OK, passed 100 tests.
! functor.identity: Falsified after 0 passed tests.
> ARG_0: One(-2147483648)
+ functor.composite: OK, passed 100 tests.

Applicative Laws

From Haskell/Applicative functors:

pure id <*> v = v                            -- Identity
pure f <*> pure x = pure (f x)               -- Homomorphism
u <*> pure y = pure ($ y) <*> u              -- Interchange
pure (.) <*> u <*> v <*> w = u <*> (v <*> w) -- Composition

We need to implement Arbitrary[Amount[A => B]]:

val gen: Gen[Amount[Int => Int]]=
  for {
    x <- Arbitrary.arbitrary[Int => Int]
    y <- Arbitrary.arbitrary[Int => Int]
    z <- Arbitrary.arbitrary[Int => Int]
    a <- Gen.oneOf(One(x), Couple(x,y), Few(x,y,z))
  } yield a

implicit val arbitrary: Arbitrary[Amount[Int => Int]] =
  Arbitrary(gen)

This reveals a lot of problems in our applicative implementation from Day 2. Let's rewrite it to be law-abiding:

implicit val applicative: Applicative[Amount] =
  new Applicative[Amount] {
    def point[A](a: => A): Amount[A] = Few(a, a, a)
    def ap[A, B](fa: => Amount[A])(f: => Amount[A => B]): Amount[B] =
      fa match {
        case One(a) =>
          f match {
            case One(g)       => One(g(a))
            case Couple(g, _) => One(g(a))
            case Few(g, _, _) => One(g(a))
          }
        case Couple(a, b) =>
          f match {
            case One(g)       => One(g(a))
            case Couple(g, h) => Couple(g(a), h(b))
            case Few(g, h, _) => Couple(g(a), h(b))
          }
        case Few(a, b, c) =>
          f match {
            case One(g)       => One(g(a))
            case Couple(g, h) => Couple(g(a), h(b))
            case Few(g, h, i) => Few(g(a), h(b), i(c))
          }
      }
  }

This looks better:

$ sbt
> test:console
scala> applicative.laws[Amount].check
+ applicative.apply.functor.invariantFunctor.identity: OK, passed 100 tests
  .
+ applicative.apply.functor.invariantFunctor.composite: OK, passed 100 test
  s.
+ applicative.apply.functor.identity: OK, passed 100 tests.
+ applicative.apply.functor.composite: OK, passed 100 tests.
+ applicative.apply.composition: OK, passed 100 tests.
+ applicative.identity: OK, passed 100 tests.
+ applicative.homomorphism: OK, passed 100 tests.
+ applicative.interchange: OK, passed 100 tests.
+ applicative.map consistent with ap: OK, passed 100 tests.

Semigroup Laws

Monoid Laws

Option as Monoid

Foldable

Day 5

A fist full of Monads

Here’s the typeclass contract:

trait Monad[F[_]] extends Applicative[F] with Bind[F] { self =>
  ////
}

To save some headache about what Few(a,b,c) >>= \_ -> Few(x,y,z) means, let's forget about Amount for now and proceed with a simple Maybe type:

implicit val monad: Monad[Maybe] =
  new Monad[Maybe] {
    def point[A](a: => A): Maybe[A] = Just(a)
    def bind[A, B](fa: Maybe[A])(f: A => Maybe[B]): Maybe[B] =
      fa match {
        case Just(a) => f(a)
        case Nada => Nada
      }
  }

This probably won't hold up to the monad laws, but let's worry about that later.

Bind

Here’s Bind’s contract:

trait Bind[F[_]] extends Apply[F] { self =>
  /** Equivalent to `join(map(fa)(f))`. */
  def bind[A, B](fa: F[A])(f: A => F[B]): F[B]
}

If we try to use the bind operators right now, we get a compile error:

Just(21) >>= { x => Just(x*2) } // value >>= is not a member of Just[Int]

We have to import the various conversions in Maybe's monad:

import Maybe.monad.monadSyntax._
Just(21) >>= { x => Just(x*2) } // 42

Monad

Unlike Haskell, Monad[F[_]] exntends Applicative[F[_]] so there’s no return vs pure issues. They both use point.

This also means that to check the monad laws, we'll need to provide both Arbitrary[Amount[Int]] and Arbitrary[Amount[Int => Int]] to ScalaCheck.

Walk the line

Here we look at monadic chaining of flatMap.

Banana on wire

Here we look at the >> operator.

for syntax

Pierre returns

Pattern matching and failure

List Monad

MonadPlus and the guard function

Plus, PlusEmpty, and ApplicativePlus

MonadPlus again

A knight’s quest

Monad laws

Day 6

for syntax again

Compare Haskell's do notation to Scala's for comprehension:

Haskell:

foo = do
  x <- Just 3
  y <- Just "!"
  Just (show x ++ y)

Scala:

def foo = for {
  x <- 3.some
  y <- "!".some
} yield x.shows + y

It appears that Eugene goes on to illustrate Scala's use of map at the end of for comprehensions, which Haskell doesn't do. In his example, Eugene shows how to finish a notation/comprehension with a function that returns a monadic value:

Haskell:

in3 start = do
  first <- moveKnight start
  second <- moveKnight first
  moveKnight second

Scala:

def in3: List[KnightPos] = for {
  first <- move
  second <- first.move
  third <- second.move
} yield third

Writer? I hardly knew her!

Whereas the Maybe monad is for values with an added context of failure, and the list monad is for nondeterministic values, Writer monad is for values that have another value attached that acts as a sort of log value.

We start by implementing the simple applyLog function:

scala> (3, "Smallish gang.") applyLog { (x) => (x > 9, "Compared gang size to 9.") }
res30: (Boolean, String) = (false,Smallish gang.Compared gang size to 9.)

We then modify applyLog to use Monoid and |+| rather than String and + for the right-hand side of those tuples.

Writer

type Writer[+W, +A] = WriterT[Id, W, A]

It's interesting that Writer is covariant in both W and A. This means that Writer[LogImpl, ValueImpl] is a subtype of Writer[LogTrait, ValueTrait].

WriterT

For an example of a non-Scalaz WriterT[Option,W,A], see Functional debugging in Scala

WriterT simplifies to:

sealed trait WriterT[F[+_], +W, +A] { self =>
  val run: F[(W, A)]

  def written(implicit F: Functor[F]): F[W] =
    F.map(run)(_._1)
  def value(implicit F: Functor[F]): F[A] =
    F.map(run)(_._2)
}

WriterOps adds the strangely-named set function to make Writers out of things:

final class WriterOps[A](self: A) {
  def set[W](w: W): Writer[W, A] = WriterT.writer(w -> self)

  def tell: Writer[A, Unit] = WriterT.tell(self)
}

I have often seen set[A](x: A) provided as a standard Writer utility, which I guess is where WriterOps#set gets its name:

val log: Writer[List[String], Unit] =
  WriterT.writer((Nil, ()))

def set(x: String): Writer[List[String], Unit] =
  WriterT.writer((List(x), ()))

def multWithLog: Writer[List[String], Int] = for {
  _ <- log
  a  = 3
  _ <- set("Got number: " + a)
  b  = 5
  _ <- set("Got number: " + b)
} yield a * b

val result: (List[String], Int) = multWithLog run
// (List(Got number: 3, Got number: 5),15)

There's also MonadTell to make Writers:

scala> MonadTell[Writer, String].point(3).run
res64: (String, Int) = ("",3)

Using for syntax with Writer

We start to see the benefit of Writer when using it in a for comprehension. The key is that the log (or accumulator, or monoid, etc.) is hidden from us, so we don't have to think about it. Logging is abstracted away from us.

def logNumber(x: Int): Writer[List[String], Int] =
  x.set(List("Got number: " + x.shows))

def multWithLog: Writer[List[String], Int] = for {
  a <- logNumber(3)
  b <- logNumber(5)
} yield a * b

val result: (List[String], Int) = multWithLog run
// (List(Got number: 3, Got number: 5),15)

Adding logging to program

More of the above.

Inefficient List construction

This section goes on to talk about concatenation performances of List and Vector.

Comparing performance

More of the above.

Reader

Not only is the function type (->) r a functor and an applicative functor, but it’s also a monad.

val addStuff: Int => Int = for {
  a <- (_: Int) * 2
  b <- (_: Int) + 10
} yield a + b

// addStuff(x) = (x * 2) + (x + 10)

val x: Int = addStuff(3) // 19

I've also often seen get[A] provided as a standard Reader utility:

def get[A]: A => A = identity

val addStuff: Int => Int = for {
  e <- get[Int]
  a  = e * 2
  b  = e + 10
} yield a + b

// addStuff(x) = (x * 2) + (x + 10)

val x: Int = addStuff(3) // 19

Day 7

Applicative Builder

We're looking again (see day 2) at the TIE fighter operator |@|:

final def |@|[B](fb: F[B]): ApplicativeBuilder[F, A, B]

DSL for constructing Applicative expressions.

(f1 |@| f2 |@| ... |@| fn)((v1, v2, ... vn) => ...) is an alternative to Apply[F].applyN(f1, f2, ..., fn)((v1, v2, ... vn) => ...)

(f1 |@| f2 |@| ... |@| fn).tupled is an alternative to Apply[F].applyN(f1, f2, ..., fn)(TupleN.apply _)

Warning: each call to |@| leads to an allocation of wrapper object. For performance sensitive code, consider using scalaz.Apply#applyN directly.

Examples:

scala> (3.some |@| 5.some) {_ + _}
res18: Option[Int] = Some(8)
scala> val f = ({(_: Int) * 2} |@| {(_: Int) + 10}) {_ + _}
f: Int => Int = <function1>

Tasteful stateful computations

Time for the state monad, oh boy! \o/

State and StateT

State is just an alias for StateT of Id:

type State[S, +A] = StateT[Id, S, A]

Holy variance, Batman:

trait StateT[F[+_], S, +A] { self =>
  /** Run and return the final value and state in the context of `F` */
  def apply(initial: S): F[(S, A)]

  /** An alias for `apply` */
  def run(initial: S): F[(S, A)] = apply(initial)

  /** Calls `run` using `Monoid[S].zero` as the initial state */
  def runZero(implicit S: Monoid[S]): F[(S, A)] =
    run(S.zero)
}

Using a Monoid instance to provide runZero is pretty clever. This can be used to build interpreters with less noise about constructing initial state.

Getting and setting state

The State object extends StateFunctions, which has lots of goodies:

trait StateFunctions {
  def constantState[S, A](a: A, s: => S): State[S, A] =
    State((_: S) => (s, a))
  def state[S, A](a: A): State[S, A] =
    State((_ : S, a))
  def init[S]: State[S, S] = State(s => (s, s))
  def get[S]: State[S, S] = init
  def gets[S, T](f: S => T): State[S, T] = State(s => (s, f(s)))
  def put[S](s: S): State[S, Unit] = State(_ => (s, ()))
  def modify[S](f: S => S): State[S, Unit] = State(s => {
    val r = f(s);
    (r, ())
  })
  /**
   * Computes the difference between the current and previous values of `a`
   */
  def delta[A](a: A)(implicit A: Group[A]): State[A, A] = State{
    (prevA) =>
      val diff = A.minus(a, prevA)
      (diff, a)
  }
}

Mutations using State tend to have the type State[Unit], meaning they might alter state in some way, but they don't return anything meaningful to the interpreter.

\/

In Scalaz, \/ is mostly similar to Either, but with lots of extra functions, methods, projections, etc.

Validation

In Scalaz, Validation is also similar to Either, but geared specifically for encapsulating success vs. failure.

NonEmptyList

When using Validation, it's common to collect errors as we go. When we have a failure, we should expect at least on error, so we use NonEmptyList to guarantee that head exists.

scala> "event 1 ok".successNel[String]
res48: scalaz.ValidationNEL[String,String] = Success(event 1 ok)

scala> "event 1 failed!".failureNel[String]
res49: scalaz.ValidationNEL[String,String] = Failure(NonEmptyList(event 1 failed!))

scala> ("event 1 ok".successNel[String] |@| "event 2 failed!".failureNel[String] |@| "event 3 failed!".failureNel[String]) {_ + _ + _}
res50: scalaz.Unapply[scalaz.Apply,scalaz.ValidationNEL[String,String]]{type M[X] = scalaz.ValidationNEL[String,X]; type A = String}#M[String] = Failure(NonEmptyList(event 2 failed!, event 3 failed!))

Day 8

Some useful monadic functions

join

In Scalaz, join (aka μ) is flatten.

filterM

Monad[F].filterM[A](List[A])((A) => F[Boolean]): F[List[A]]

foldLeftM

Left-associative, monadic fold of a structure.

Foldable[F].foldLeftM[G, A, B](F[A], B)((B, A) => G[B])(implicit Monad[G]): G[B]

Making a safe RPN calculator

Composing monadic functions

Kleisli

Kleisli wraps A => M[B]

Reader again

Making monads

Day 9

Start the final chapter of Learn You a Haskell, we begin with zippers.

In this chapter, we'll see how we can take some data structure and focus on a part of it in a way that makes changing its elements easy and walking around it efficient.

From Hackage:

The Zipper is a data structure that allows typed navigation on a value. It maintains a subterm as a current point of focus. The rest of the value is the context. Focus and context are automatically updated when navigating up, down, left or right in the value. The term that is in focus can also be modified.

This reminds me of lenses, and I found this comparison of the two:

Zippers are akin to cursors: they allow to traverse trees in an ordered manner. Their usual operations are up, down, left, right and edit. (names may vary depending on impl)

Lenses are some sort of generalized keys (as in "keys of an associative datastructure"). The structure does not need to be ordered. Their usual operations are fetch and putback and are very similar to get and assoc. (names may vary depending on impl)

See also From Zipper to Lens from FPComplete.

We will learn about lenses on day 11.

Tree

With Scalaz, we can create trees using node and leaf:

def freeTree: Tree[Char] =
  'P'.node(
    'O'.node(
      'L'.node('N'.leaf, 'T'.leaf),
      'Y'.node('S'.leaf, 'A'.leaf)),
    'L'.node(
      'W'.node('C'.leaf, 'R'.leaf),
      'A'.node('A'.leaf, 'C'.leaf)))

Without zippers, changing values requires manual traversal, in this case via pattern matching:

def changeToP(tree: Tree[Char]): Tree[Char] = tree match {
  case Tree.Node(x, Stream(
    l, Tree.Node(y, Stream(
      Tree.Node(_, Stream(m, n)), r)))) =>
    x.node(l, y.node('P'.node(m, n), r))
}

Interestingly, child nodes of a tree (called "subforests") are modelled as a stream of trees:

sealed trait Tree[A] {
  /** The label at the root of this tree. */
  def rootLabel: A
  /** The child nodes of this tree. */
  def subForest: Stream[Tree[A]]
}

TreeLoc

Scalaz gives us a Tree zipper called TreeLoc which, among other things, gives us getChild:

def getChild(n: Int): Option[TreeLoc[A]] = ...

Now we can traverse our tree. To find 'W', we want the first child of the second child of the root:

freeTree.loc.getChild(2) >>= {_.getChild(1)} >>= {_.getLabel.some}

To change 'W', we use modifyLabel:

def modifyLabel(f: A => A): TreeLoc[A] = ...
freeTree.loc.getChild(2) >>= {_.getChild(1)} >>= {_.modifyLabel({_ => 'P'}).some}

Focusing on Streams

This is more or less the same as tree traversal.

Id

Scalaz has a funny-looking identity type:

type Id[+X] = X

This "can be thought of as Tuple1, but with no runtime representation."

We've already encountered Id several times when looking at monad transformers, as many monads tend to be implemented in terms of a monad transformer on Id:

type Reader[E, A] = ReaderT[Id, E, A]
type ReaderT[F[_], E, A] = Kleisli[F, E, A]

Scalaz provides a bunch of variously useful operations in IdOps, mainly for tasty syntax.

Id also gives us a way to lift values without actually lifting them:

scala> val inc: Int => Int = x => x + 1
inc: Int => Int = <function1>

scala> 41 <*> inc
<console>:24: error: value <*> is not a member of Int
              41 <*> inc
                 ^

scala> (41:Id[Int]) <*> inc
res20: scalaz.Scalaz.Id[Int] = 42

Length

trait Length[F[_]]  { self =>
  def length[A](fa: F[A]): Int
}

Not too exciting, but in a parallel universe it could replace the standard library's SeqLike.

Index

trait Index[F[_]]  { self =>
  def index[A](fa: F[A], i: Int): Option[A]
}

Also not terribly exciting, but an interesting alternative to the standard library's approach.

Day 10

Day ten is all about monad transformers.

hoist

One of the interesting challenges I have run into when using monad transformers is that, when combining instances in a for comprehension (or just using map and flatMap), they all have to have matching types. For example:

val halve: ReaderT[Option,Int,Int] =
  ReaderT { x: Int => if (x % 2 == 1) None else Some(x / 2) }

val plusTen: Reader[Int,Int] =
  Reader { x: Int => x + 10 }

We can't combine these in a for comprehension, because they have incompatible types. plusTen is a Reader, or a ReaderT[Id]. We need a way to convert Id values into Option values, so we can convert plusTen into a ReaderT[Option].

Enter hoist:

val idToOption: Id ~> Option =
  new NaturalTransformation[Id, Option] {
    def apply[A](fa: Id[A]): Option[A] = Some(fa)
  }

val addStuff: ReaderT[Option,Int,Int] =
  for {
    a <- halve
    b <- Kleisli.kleisliMonadTrans.hoist(idToOption).apply(plusTen)
    c  = a + b
  } yield c

Type lambda hacking

Things get particularly nasty when building new monad transformers:

def hoist[M[_],N[_],E](f: M ~> N):
  ({ type X[Y] = MyReaderT[M,E,Y]})#X ~> ({ type W[Y] = MyReaderT[N,E,Y]})#W =
    new NaturalTransformation[({ type X[Y] = MyReaderT[M,E,Y]})#X,
                              ({ type W[Y] = MyReaderT[N,E,Y]})#W] {
      def apply[A](rm: MyReaderT[M,E,A]): MyReaderT[N,E,A] =
        MyReaderT(e => f(rm.run(e)))
    }

Holy type lamndas, Batman. We can clean this up a bit by making a new type that locks down two of MyReader's three type parameters:

class MyReaderTFE[F[_],E]() {
  type X[A] = MyReaderT[F,E,A]
}

def hoist[M[_],N[_],E](f: M ~> N): MyReaderTFE[M,E]#X ~> MyReaderTFE[N,E]#X =
  new NaturalTransformation[MyReaderTFE[M,E]#X, MyReaderTFE[N,E]#X] {
    def apply[A](rm: MyReaderT[M,E,A]): MyReaderT[N,E,A] =
      MyReaderT(e => f(rm.run(e)))
  }

kind-projector

Our type lambda hacking is nice, but we can do better. Ideally, Scala would be smart enough to understand that MyReaderT[M,E,_] means ({ type X[Y] = MyReaderT[M,E,Y]})#X. It isn't but we can fix that with macros. The kind-projector sbt plugin does this for us:

def hoist[M[_],N[_],E](f: M ~> N): MyReaderT[M,E,?] ~> MyReaderT[N,E,?] =
  new NaturalTransformation[MyReaderT[M,E,?], MyReaderT[N,E,?]] {
    def apply[A](rm: MyReaderT[M,E,A]): MyReaderT[N,E,A] =
      MyReaderT(e => f(rm.run(e)))
  }

Day 11

Go turtle go

The problem we wish to solve is to clean up nested case class copies that are much simpler to do in mutable code:

// imperative
a.b.c.d.e += 1

// functional
a.copy(
  b = a.b.copy(
    c = a.b.c.copy(
      d = a.b.c.d.copy(
        e = a.b.c.d.e + 1
))))

Lens

Lens is a type alias for LensT[Id, A, B].

LensT

LensT is a trait, but it's not too clear how it's used:

sealed trait LensT[F[+_], A, B] {
  def run(a: A): F[Store[B, A]]
  def apply(a: A): F[Store[B, A]] = run(a)
  ...
}

LensT inherits lots of methods:

sealed trait LensT[F[+_], A, B] {
  def get(a: A)(implicit F: Functor[F]): F[B] =
    F.map(run(a))(_.pos)
  def set(a: A, b: B)(implicit F: Functor[F]): F[A] =
    F.map(run(a))(_.put(b))
  /** Modify the value viewed through the lens */
  def mod(f: B => B, a: A)(implicit F: Functor[F]): F[A] = ...
  def =>=(f: B => B)(implicit F: Functor[F]): A => F[A] =
    mod(f, _)
  /** Modify the portion of the state viewed through the lens and return its new value. */
  def %=(f: B => B)(implicit F: Functor[F]): StateT[F, A, B] =
    mods(f)
  /** Lenses can be composed */
  def compose[C](that: LensT[F, C, A])(implicit F: Bind[F]): LensT[F, C, B] = ...
  /** alias for `compose` */
  def <=<[C](that: LensT[F, C, A])(implicit F: Bind[F]): LensT[F, C, B] = compose(that)
  def andThen[C](that: LensT[F, B, C])(implicit F: Bind[F]): LensT[F, A, C] =
    that compose this
  /** alias for `andThen` */
  def >=>[C](that: LensT[F, B, C])(implicit F: Bind[F]): LensT[F, A, C] = andThen(that)
}

Store

Store is a type alias for StoreT[Id, A, B].

A Store wraps a setter A => B => A and getter A => B.

Using Lens

I toyed around with some nested case classes, and came up with the following:

case class Street(name: String)
case class Address(street: Street)
case class Company(name: String, address: Address)
case class Employee(name: String, company: Company)
val companyAddress: Lens[Company, Address] =
  Lens.lensu[Company, Address] (
    (a, value) => a.copy(address = value),
    _.address
  )

val addressStreet: Lens[Address, Street] =
  Lens.lensu[Address, Street] (
    (a, value) => a.copy(street = value),
    _.street
  )

val streetName: Lens[Street, String] =
  Lens.lensu[Street, String] (
    (a, value) => a.copy(name = value),
    _.name
  )

val companyStreetName: Lens[Company, String] =
  companyAddress >=> addressStreet >=> streetName

val capitalizeStreetName1: Company => Company =
  company => companyStreetName mod(_.capitalize, company)

val capitalizeStreetName2: Company => Company =
  companyStreetName =>= { _.capitalize }

val capitalizeStreetName3: State[Company, String] =
  (companyStreetName %= { x: String => x.capitalize })

val moveCompany: Company => Company =
  company => companyStreetName set(company, "Somewhere Else Pl.")
val street = Street("main st.")
val address = Address(street)
val company = Company("The Very Big Corporation", address)
val employee = Employee("Bob Worker", company)

companyStreetName get company // "main st."
companyStreetName get capitalizeStreetName1(company) // "Main st."
companyStreetName get capitalizeStreetName2(company) // "Main st."
companyStreetName get (capitalizeStreetName3 run company)._1 // "Main st."
companyStreetName get moveCompany(company) // "Somewhere Else Pl."

Lens as a State monad

Lens laws

  1. if I get twice, I get the same answer
  2. if I get, then set it back, nothing changes.
  3. if I set, then get, I get what I set.
  4. if I set twice then get, I get the second thing I set.