May 31, 2015

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

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"
```

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.

- The key to folds -- provides the "starting value" and the "squashing" function

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)
}
```

- Implicit resolution includes the companion object of the type you seek

- This is where we want to enrich types
- Not to provide the core functionality of monoids and folds
- To provide the syntax that enable monoids and folds

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

```
implicit val equal: Equal[Amount] =
new Equal[Amount] {
def equal(a: Amount, b: Amount): Boolean = a == b
}
```

```
assert(few === few)
assert(couple =/= few)
```

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

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

`assert(couple.show === "Couple")`

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

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

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.

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.

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.

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

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.

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`

.

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

`^(f1, f2) { ... }`

vs `|@|`

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

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

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 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())
```

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.

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

From HaskellWiki/Functor:

All instances of Functor should obey:

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

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

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

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

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.

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

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.

Here we look at monadic chaining of `flatMap`

.

Here we look at the `>>`

operator.

`for`

syntax`for`

syntax againCompare 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 `Writer`

s 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 `Writer`

s:

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

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

*More of the above.*

This section goes on to talk about concatenation performances of `List`

and `Vector`

.

*More of the above.*

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

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

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.

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!))
```

`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]`

Kleisli wraps `A => M[B]`

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

orderedmanner. 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}`

`Stream`

sThis 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 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
```

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)))
}
```

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)))
}
```

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`

.

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

`State`

monad`Lens`

laws

- if I get twice, I get the same answer
- if I get, then set it back, nothing changes.
- if I set, then get, I get what I set.
- if I set twice then get, I get the second thing I set.