独習 Scalaz: 4日目

in

更新された html5版があるので、よろしくお願いします。

昨日は、カインドと型について考え、Tagged type を探検して、さまざまな型の 2項演算を抽象化する方法としての SemigroupMonoid をみてみた。

いくつかの感想や意見もいただいた。まず、kind 計算機だけど paulp さんから Option.type みたいにコンパニオン型を使ったらどうかと教えてもらった。更新したバージョンを使うとこう書ける:

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

Jason Zaugg さんにもコメントをもらった:

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

この辺りで一度立ち止まって、行儀の良い型クラスが従うべき法則についても議論すべきじゃないですか。

Learn You a Haskell for Great Good の型クラスの法則に関しては全て飛ばしてきたところを、パトカーに止められた形だ。恥ずかしい限りだ。

Functor則

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.

言い換えると、

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.

言い換えると、

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

これらの法則は Functor の実装者が従うべき法則で、コンパイラはチェックしてくれない。Scalaz 7 にはコードでこれを記述した FunctorLaw trait が入っている:

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

それだけじゃなく、これらを任意の値でテストする ScalaCheck へのバインディングもついてきてる。以下が REPL からこれを実行するための build.sbt だ。これは今まで使ってきた Scalaz 7.0.0-M3/Scala 2.10.0-M7 という組み合わせよりも少し古いバージョンに戻っている。最新版では scalaz-scalacheck-binding が公開されていないからだ:

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

通常の sbt console のかわりに、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> 

List が Functor則を満たすかテストしてる:

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

法則を破る

本にあわせて、法則を破ってみよう:

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)

これは最初の法則を破っている。検知できるかみてみよう。

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
                          ^

COption[A] の「任意」の値を暗黙に提供しなきゃいけないみたいだ:

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

これは面白い。ScalaCheck そのものは map メソッドを提供しないけど、Scalaz が Functor[Arbitrary] として注入している! あまりぱっとしない任意の COption だけど、ScalaCheck をよく知らないのでこれでいいとする。

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>

期待通りテストは失敗した。

Applicative則

これが 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 も詳細は飛ばしているので、僕も見逃してもらう。

Semigroup則

これが、Semigroup則だ:

  /**
   * 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))
  }

1 * (2 * 3)(1 * 2) * 3 が満たされるべきで、これは結合律 (associative) と呼ばれるのは覚えているよね。

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

Monoid則

これが Monoid則 だ:

  /**
   * 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))
  }

この法則は簡単だ。単位元 (identity value) を左右のどちらに |+| (mappend) しても同じ値が返ってくるということだ。乗算で確認:

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

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.

Monoid としての Option

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.

Scalaz がこうなっているか確認しよう。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
  }

実装はシンプルで良い感じだ。Context bound の A: SemigroupA|+| をサポートしなければいけないと言っている。残りはパターンマッチングだ。本の言うとおりの振る舞いだ。

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

ちゃんと動く。

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 は newtype を使って First 型コンストラクタを実装している。Scalaz 7 は強力な 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.

これは 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!

Scalaz でこれに対応するものも Foldable と呼ばれている。型クラスのコントラクトも見てみよう:

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

演算子はこれだ:

/** 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)
 
  ////
}

これはスゴい。コレクションライブラリさながらだけど、Order などの型クラスを駆使している。畳込みをやってみよう:

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

これらは標準ライブラリにも入っている。foldMap 演算子も試してみよう。Monoid[A]zero|+| を提供するから、畳込みに十分な情報がある。Foldable がいつも Monoid を持っているとは限らないので、[B: Monoid] である A => B 関数が必要だ:

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

Tags.Disjunction(true) と一つ一つ書きだして |+| でつなぐよりずっと楽だ。

続きはまた後で。今週は出張なので、ちょっとペースは落ちるかも。