# learning Scalaz: day 4

Hey there. There's an updated html5 book version, if you want.

Yesterday we reviewed kinds and types, explored Tagged type, and started looking at `Semigroup`

and `Monoid`

as a way of abstracting binary operations over various types.

I've gotten a few feedbacks. First, paulp suggested that I could use companion type like `Option.type`

for our `kind`

calculator. Using the updated version, we get the following:

scala> kind[Functor.type] res1: String = Functor's kind is (* -> *) -> *. This is a type constructor that takes type constructor(s): a higher-kinded type.

Also a comment from Jason Zaugg:

This might be a good point to pause and discuss the laws by which a well behaved type class instance must abide.

I've been skipping all the sections in Learn You a Haskell for Great Good about the laws and we got pulled over.

### Functor Laws

LYAHFGG:

All functors are expected to exhibit certain kinds of functor-like properties and behaviors.

...

The first functor law states that if we map the id function over a functor, the functor that we get back should be the same as the original functor.

In other words,

scala> List(1, 2, 3) map {identity} assert_=== List(1, 2, 3)

The second law says that composing two functions and then mapping the resulting function over a functor should be the same as first mapping one function over the functor and then mapping the other one.

In other words,

scala> (List(1, 2, 3) map {{(_: Int) * 3} map {(_: Int) + 1}}) assert_=== (List(1, 2, 3) map {(_: Int) * 3} map {(_: Int) + 1})

These are laws the implementer of the functors must abide, and not something the compiler can check for you. Scalaz 7 ships with `FunctorLaw`

traits that describes this in code:

trait FunctorLaw { /** The identity function, lifted, is a no-op. */ def identity[A](fa: F[A])(implicit FA: Equal[F[A]]): Boolean = FA.equal(map(fa)(x => x), fa) /** * A series of maps may be freely rewritten as a single map on a * composed function. */ def associative[A, B, C](fa: F[A], f1: A => B, f2: B => C)(implicit FC: Equal[F[C]]): Boolean = FC.equal(map(map(fa)(f1))(f2), map(fa)(f2 compose f1)) }

Not only that, it ships with ScalaCheck bindings to test these properties using arbiterary values. Here's the `build.sbt`

to check from REPL. Note this is using slightly older version of Scala 2.10 and Scalaz 7 milestones instead of 7.0.0-M3/2.10.0-M7 that we have been using because scalaz-scalacheck-binding is not there for it:

scalaVersion := "2.10.0-M6" resolvers += "Typesafe Snapshots" at "http://repo.typesafe.com/typesafe/snapshots/" libraryDependencies ++= Seq( "org.scalaz" % "scalaz-core" % "7.0.0-M2" cross CrossVersion.full, "org.scalaz" % "scalaz-scalacheck-binding" % "7.0.0-M2" % "test" cross CrossVersion.full ) scalacOptions += "-feature" initialCommands in console := "import scalaz._, Scalaz._" initialCommands in console in Test := "import scalaz._, Scalaz._, scalacheck.ScalazProperties._, scalacheck.ScalazArbitrary._,scalacheck.ScalaCheckBinding._"

Instead of the usual `sbt console`

, run `sbt test:console`

:

$ sbt test:console [info] Starting scala interpreter... [info] import scalaz._ import Scalaz._ import scalacheck.ScalazProperties._ import scalacheck.ScalazArbitrary._ import scalacheck.ScalaCheckBinding._ Welcome to Scala version 2.10.0-M6 (Java HotSpot(TM) 64-Bit Server VM, Java 1.6.0_33). Type in expressions to have them evaluated. Type :help for more information. scala>

Here's how you test if `List`

meets the functor laws:

scala> functor.laws[List].check + functor.identity: OK, passed 100 tests. + functor.associative: OK, passed 100 tests.

### Breaking the law

Following the book, let's try breaking the law.

scala> :paste // Entering paste mode (ctrl-D to finish) sealed trait COption[+A] {} case class CSome[A](counter: Int, a: A) extends COption[A] case object CNone extends COption[Nothing] implicit def coptionEqual[A]: Equal[COption[A]] = Equal.equalA implicit val coptionFunctor = new Functor[COption] { def map[A, B](fa: COption[A])(f: A => B): COption[B] = fa match { case CNone => CNone case CSome(c, a) => CSome(c + 1, f(a)) } } // Exiting paste mode, now interpreting. defined trait COption defined class CSome defined module CNone coptionEqual: [A]=> scalaz.Equal[COption[A]] coptionFunctor: scalaz.Functor[COption] = $anon$1@42538425 scala> (CSome(0, "ho"): COption[String]) map {(_: String) + "ha"} res4: COption[String] = CSome(1,hoha) scala> (CSome(0, "ho"): COption[String]) map {identity} res5: COption[String] = CSome(1,ho)

It's breaking the first law. Let's see if we can catch this.

scala> functor.laws[COption].check <console>:26: error: could not find implicit value for parameter af: org.scalacheck.Arbitrary[COption[Int]] functor.laws[COption].check ^

So now we have to supply "arbitrary" `COption[A]`

implicitly:

scala> import org.scalacheck.{Gen, Arbitrary} import org.scalacheck.{Gen, Arbitrary} scala> implicit def COptionArbiterary[A](implicit a: Arbitrary[A]): Arbitrary[COption[A]] = a map { a => (CSome(0, a): COption[A]) } COptionArbiterary: [A](implicit a: org.scalacheck.Arbitrary[A])org.scalacheck.Arbitrary[COption[A]]

This is pretty cool. ScalaCheck on its own does not ship `map`

method, but Scalaz injected it as a `Functor[Arbitrary]`

! Not much of an arbitrary `COption`

, but I don't know enough ScalaCheck, so this will have to do.

scala> functor.laws[COption].check ! functor.identity: Falsified after 0 passed tests. > ARG_0: CSome(0,-170856004) ! functor.associative: Falsified after 0 passed tests. > ARG_0: CSome(0,1) > ARG_1: <function1> > ARG_2: <function1>

And the test fails as expected.

### Applicative Laws

Here are the laws for Applicative:

trait ApplicativeLaw extends FunctorLaw { def identityAp[A](fa: F[A])(implicit FA: Equal[F[A]]): Boolean = FA.equal(ap(fa)(point((a: A) => a)), fa) def composition[A, B, C](fbc: F[B => C], fab: F[A => B], fa: F[A])(implicit FC: Equal[F[C]]) = FC.equal(ap(ap(fa)(fab))(fbc), ap(fa)(ap(fab)(ap(fbc)(point((bc: B => C) => (ab: A => B) => bc compose ab))))) def homomorphism[A, B](ab: A => B, a: A)(implicit FB: Equal[F[B]]): Boolean = FB.equal(ap(point(a))(point(ab)), point(ab(a))) def interchange[A, B](f: F[A => B], a: A)(implicit FB: Equal[F[B]]): Boolean = FB.equal(ap(point(a))(f), ap(f)(point((f: A => B) => f(a)))) }

LYAHFGG is skipping the details on this, so I am skipping too.

### Semigroup Laws

Here are the Semigroup Laws:

/** * A semigroup in type F must satisfy two laws: * * - '''closure''': `∀ a, b in F, append(a, b)` is also in `F`. This is enforced by the type system. * - '''associativity''': `∀ a, b, c` in `F`, the equation `append(append(a, b), c) = append(a, append(b , c))` holds. */ trait SemigroupLaw { def associative(f1: F, f2: F, f3: F)(implicit F: Equal[F]): Boolean = F.equal(append(f1, append(f2, f3)), append(append(f1, f2), f3)) }

Remember, `1 * (2 * 3)`

and `(1 * 2) * 3`

must hold, which is called *associative*.

scala> semigroup.laws[Int @@ Tags.Multiplication].check + semigroup.associative: OK, passed 100 tests.

### Monoid Laws

Here are the Monoid Laws:

/** * Monoid instances must satisfy [[scalaz.Semigroup.SemigroupLaw]] and 2 additional laws: * * - '''left identity''': `forall a. append(zero, a) == a` * - '''right identity''' : `forall a. append(a, zero) == a` */ trait MonoidLaw extends SemigroupLaw { def leftIdentity(a: F)(implicit F: Equal[F]) = F.equal(a, append(zero, a)) def rightIdentity(a: F)(implicit F: Equal[F]) = F.equal(a, append(a, zero)) }

This law is simple. I can `|+|`

(`mappend`

) identity value to either left hand side or right hand side. For multiplication:

scala> 1 * 2 assert_=== 2 scala> 2 * 1 assert_=== 2

Using Scalaz:

scala> (Monoid[Int @@ Tags.Multiplication].zero |+| Tags.Multiplication(2): Int) assert_=== 2 scala> (Tags.Multiplication(2) |+| Monoid[Int @@ Tags.Multiplication].zero: Int) assert_=== 2 scala> monoid.laws[Int @@ Tags.Multiplication].check + monoid.semigroup.associative: OK, passed 100 tests. + monoid.left identity: OK, passed 100 tests. + monoid.right identity: OK, passed 100 tests.

### Option as Monoid

LYAHFGG:

One way is to treat

`Maybe a`

as a monoid only if its type parameter a is a monoid as well and then implement mappend in such a way that it uses the mappend operation of the values that are wrapped with`Just`

.

Let's see if this is how Scalaz does it. See `std/Option.scala`

:

implicit def optionMonoid[A: Semigroup]: Monoid[Option[A]] = new Monoid[Option[A]] { def append(f1: Option[A], f2: => Option[A]) = (f1, f2) match { case (Some(a1), Some(a2)) => Some(Semigroup[A].append(a1, a2)) case (Some(a1), None) => f1 case (None, Some(a2)) => f2 case (None, None) => None } def zero: Option[A] = None }

The implementation is nice and simple. Context bound `A: Semigroup`

says that `A`

must support `|+|`

. The rest is pattern matching. Doing exactly what the book says.

scala> (none: Option[String]) |+| "andy".some res23: Option[String] = Some(andy) scala> (Ordering.LT: Ordering).some |+| none res25: Option[scalaz.Ordering] = Some(LT)

It works.

LYAHFGG:

But if we don't know if the contents are monoids, we can't use

`mappend`

between them, so what are we to do? Well, one thing we can do is to just discard the second value and keep the first one. For this, the`First a`

type exists.

Haskell is using `newtype`

to implement `First`

type constructor. Scalaz 7 does it using mightly Tagged type:

scala> Tags.First('a'.some) |+| Tags.First('b'.some) res26: scalaz.@@[Option[Char],scalaz.Tags.First] = Some(a) scala> Tags.First(none: Option[Char]) |+| Tags.First('b'.some) res27: scalaz.@@[Option[Char],scalaz.Tags.First] = Some(b) scala> Tags.First('a'.some) |+| Tags.First(none: Option[Char]) res28: scalaz.@@[Option[Char],scalaz.Tags.First] = Some(a)

LYAHFGG:

If we want a monoid on

`Maybe a`

such that the second parameter is kept if both parameters of`mappend`

are`Just`

values,`Data.Monoid`

provides a the`Last a`

type.

This is `Tags.Last`

:

scala> Tags.Last('a'.some) |+| Tags.Last('b'.some) res29: scalaz.@@[Option[Char],scalaz.Tags.Last] = Some(b) scala> Tags.Last(none: Option[Char]) |+| Tags.Last('b'.some) res30: scalaz.@@[Option[Char],scalaz.Tags.Last] = Some(b) scala> Tags.Last('a'.some) |+| Tags.Last(none: Option[Char]) res31: scalaz.@@[Option[Char],scalaz.Tags.Last] = Some(a)

### Foldable

LYAHFGG:

Because there are so many data structures that work nicely with folds, the

`Foldable`

type class was introduced. Much like`Functor`

is for things that can be mapped over, Foldable is for things that can be folded up!

The equivalent in Scalaz is also called `Foldable`

. Let's see the typeclass contract:

trait Foldable[F[_]] { self => /** Map each element of the structure to a [[scalaz.Monoid]], and combine the results. */ def foldMap[A,B](fa: F[A])(f: A => B)(implicit F: Monoid[B]): B /**Right-associative fold of a structure. */ def foldRight[A, B](fa: F[A], z: => B)(f: (A, => B) => B): B ... }

Here are the operators:

/** Wraps a value `self` and provides methods related to `Foldable` */ trait FoldableOps[F[_],A] extends Ops[F[A]] { implicit def F: Foldable[F] //// final def foldMap[B: Monoid](f: A => B = (a: A) => a): B = F.foldMap(self)(f) final def foldRight[B](z: => B)(f: (A, => B) => B): B = F.foldRight(self, z)(f) final def foldLeft[B](z: B)(f: (B, A) => B): B = F.foldLeft(self, z)(f) final def foldRightM[G[_], B](z: => B)(f: (A, => B) => G[B])(implicit M: Monad[G]): G[B] = F.foldRightM(self, z)(f) final def foldLeftM[G[_], B](z: B)(f: (B, A) => G[B])(implicit M: Monad[G]): G[B] = F.foldLeftM(self, z)(f) final def foldr[B](z: => B)(f: A => (=> B) => B): B = F.foldr(self, z)(f) final def foldl[B](z: B)(f: B => A => B): B = F.foldl(self, z)(f) final def foldrM[G[_], B](z: => B)(f: A => ( => B) => G[B])(implicit M: Monad[G]): G[B] = F.foldrM(self, z)(f) final def foldlM[G[_], B](z: B)(f: B => A => G[B])(implicit M: Monad[G]): G[B] = F.foldlM(self, z)(f) final def foldr1(f: (A, => A) => A): Option[A] = F.foldr1(self)(f) final def foldl1(f: (A, A) => A): Option[A] = F.foldl1(self)(f) final def sumr(implicit A: Monoid[A]): A = F.foldRight(self, A.zero)(A.append) final def suml(implicit A: Monoid[A]): A = F.foldLeft(self, A.zero)(A.append(_, _)) final def toList: List[A] = F.toList(self) final def toIndexedSeq: IndexedSeq[A] = F.toIndexedSeq(self) final def toSet: Set[A] = F.toSet(self) final def toStream: Stream[A] = F.toStream(self) final def all(p: A => Boolean): Boolean = F.all(self)(p) final def ∀(p: A => Boolean): Boolean = F.all(self)(p) final def allM[G[_]: Monad](p: A => G[Boolean]): G[Boolean] = F.allM(self)(p) final def anyM[G[_]: Monad](p: A => G[Boolean]): G[Boolean] = F.anyM(self)(p) final def any(p: A => Boolean): Boolean = F.any(self)(p) final def ∃(p: A => Boolean): Boolean = F.any(self)(p) final def count: Int = F.count(self) final def maximum(implicit A: Order[A]): Option[A] = F.maximum(self) final def minimum(implicit A: Order[A]): Option[A] = F.minimum(self) final def longDigits(implicit d: A <:< Digit): Long = F.longDigits(self) final def empty: Boolean = F.empty(self) final def element(a: A)(implicit A: Equal[A]): Boolean = F.element(self, a) final def splitWith(p: A => Boolean): List[List[A]] = F.splitWith(self)(p) final def selectSplit(p: A => Boolean): List[List[A]] = F.selectSplit(self)(p) final def collapse[X[_]](implicit A: ApplicativePlus[X]): X[A] = F.collapse(self) final def concatenate(implicit A: Monoid[A]): A = F.fold(self) final def traverse_[M[_]:Applicative](f: A => M[Unit]): M[Unit] = F.traverse_(self)(f) //// }

That was impressive. Looks almost like the collection libraries, except it's taking advantage of typeclasses like `Order`

. Let's try folding:

scala> List(1, 2, 3).foldRight (1) {_ * _} res49: Int = 6 scala> 9.some.foldLeft(2) {_ + _} res50: Int = 11

These are already in the standard library. Let's try the `foldMap`

operator. `Monoid[A]`

gives us `zero`

and `|+|`

, so that's enough information to fold things over. Since we can't assume that `Foldable`

contains a monoid we need a function to change from `A => B`

where `[B: Monoid]`

:

scala> List(1, 2, 3) foldMap {identity} res53: Int = 6 scala> List(true, false, true, true) foldMap {Tags.Disjunction} res56: scalaz.@@[Boolean,scalaz.Tags.Disjunction] = true

This surely beats writing `Tags.Disjunction(true)`

for each of them and connecting them with `|+|`

.

We will pick it up from here later. I'll be out on a business trip, it might slow down.

- Login to post comments