Herding Cats

Day0 多相性

parametric polymorphism

型変数を含む(≒ジェネリクス?)

def head[A](xs: List[A]): A = xs(0)

派生型による多相(subtype polymorphism)

で実現できるが型ごとにmixinする必要あり柔軟性に欠ける

def plus[A](a1: A, a2: A): A = ???
 
trait PlusIntf[A] {
  def plus(a2: A): A
}
 
def plusBySubtype[A <: PlusIntf[A]](a1: A, a2: A): A = a1.plus(a2)

アドホック多相

trait CanPlus[A] {
  def plus(a1: A, a2: A): A
}
 
def plus[A: CanPlus](a1: A, a2: A): A = implicitly[CanPlus[A]].plus(a1, a2)

ちなみに Int などを暗黙的に CanPlus にしたいとき

implicit def intToCanPlus(i: Int) = new CanPlus[Int] {
  override def add(other: Int) = i + other
}

sum関数を一般化してく

def sum(xs: List[Int]): Int = xs.foldLeft(0) { _ + _ }

Intのモノイドを定義

object IntMonoid {
  def mappend(a: Int, b: Int): Int = a + b
  def mzero: Int = 0
}
 
def sum(xs: List[Int]): Int = xs.foldLeft(IntMonoid.mzero)(IntMonoid.mappend)

モノイドを抽象化

package example
trait Monoid[A] {
  def mappend(a: A, b: A): A
  def mzero: A
}
 
object Monoid {
  implicit val IntMonoid: Monoid[Int] = new Monoid[Int] {
    def mappend(a: Int, b: Int): Int = a + b
    def mzero: Int = 0
  }
}
 
object Hello {
  def sum[A: Monoid](xs: List[A])(implicit m: Monoid[A]): A = xs.foldLeft(m.mzero)(m.mappend)
  def main(args: Array[String]) {
    println(sum(List(1, 2, 3)))
  }
}

foldLeftを一般化

package example
 
trait Monoid[A] {
  def mappend(a: A, b: A): A
  def mzero: A
}
 
trait FoldLeft[F[_]] {
  def foldLeft[A, B](xs: F[A], b: B, f: (B, A) => B): B
}
 
object Monoid {
  implicit val IntMonoid: Monoid[Int] = new Monoid[Int] {
    def mappend(a: Int, b: Int): Int = a + b
    def mzero: Int = 0
  }
}
 
object FoldLeft {
  implicit val FoldLeftList: FoldLeft[List] = new FoldLeft[List] {
    def foldLeft[A, B](xs: List[A], b: B, f: (B, A) => B) = xs.foldLeft(b)(f)
  }
}
 
object Hello {
  def sum[M[_]: FoldLeft, A: Monoid](xs: M[A])(implicit m: Monoid[A], fl: FoldLeft[M]): A = fl.foldLeft(xs, m.mzero, m.mappend)
 
  def main(args: Array[String]) {
    println(sum(List(1, 2, 3)))
  }
}

メソッド注入

• simulacrum を使う,
  • build.sbt に追加, モノイドを別ファイルに

import simulacrum._
 
@typeclass trait Monoid[A] {
  @op("|+|") def mappend(a: A, b: A): A
  def mzero: A
}
 
println(3 |+| 4) // 7
println("a" |+| "b") // ab

Day1

cats 導入

• Eq: "===","=!="
• Order: < , >, <=, >=, min ,max 等の演算を可能に
• PartialOrder
• Show
• Read, Enum はCatsにはない

import cats._, cats.data._, cats.implicits._
 
println(1 < 2) // true
println(1 tryCompare 2) // Some(-1)
println(1.0 tryCompare Double.NaN) // Some(-1)

型クラス

data TrafficLight = Red | Yellow | Green

package example
 
import cats._, cats.data._, cats.implicits._
 
sealed trait TrafficLight
object TrafficLight {
  def red: TrafficLight = Red
  def yellow: TrafficLight = Yellow
  def green: TrafficLight = Green
 
  case object Red extends TrafficLight
  case object Yellow extends TrafficLight
  case object Green extends TrafficLight
}
 
object Hello {
  implicit val trafficLightEq: Eq[TrafficLight] = new Eq[TrafficLight] {
    def eqv(a1: TrafficLight, a2: TrafficLight): Boolean = a1 == a2
  }
 
  def main(args: Array[String]) {
    println(TrafficLight.red === TrafficLight.yellow) // false
  }
}

Day2

simulacrumで型クラスを作る

package example
 
import simulacrum._
 
@typeclass trait CanTruthy[A] { self =>
  def truthy(a: A): Boolean
}
 
object CanTruthy {
  def fromTruthy[A](f: A => Boolean): CanTruthy[A] = new CanTruthy[A] {
    def truthy(a: A): Boolean = f(a)
  }
 
  implicit val intCanTruthy: CanTruthy[Int] = CanTruthy.fromTruthy({
    case 0 => false
    case _ => true
  })
}
 
println(10.truthy) // true

Functor

“全体を写せる” 型クラス

@typeclass trait Functor[F[_]] extends functor.Invariant[F] { self =>
  def map[A, B](fa: F[A])(f: A => B): F[B]
 
  ....
}
 
println(Functor[List].map(List(1, 2, 3)) { _ + 1 }) // [2, 3, 4]
println((Right(1): Either[String, Int]) map { _ + 1 }) // Right(2)
 
val h = ((x: Int) => x + 1) map { _ * 7 }
println(h(3)) // 28

関数の合成 $\circ$ で同じことをするにはj

fmap (*3) (+100) 1 // 303
(*3) . (+100) $ 1 // 303

関数の持ち上げ

fmapは lifting ができる(a -> bをとってf a -> f bを返す)

fmap (*2)
(*2) :: (Num a, Functor f) => f a -> f a

val lifted = Functor[List].lift {(_: Int) * 2}
println(lifted(List(1, 2, 3))) // List(2, 4, 6)
 
val a = List(1, 2, 3) fproduct {(_: Int) * 2}
println(a) // List((1,2), (2,4), (3,6))
 
val b = List(1, 2, 3) as "x"
println(b) // List(x, x, x)

Functor則

1. id で移した場合値は不変
2. x map (f map g) === x map f map g

val f = {(_: Int) * 3}
val g = {(_: Int) + 1}
val x: Either[String, Int] = Right(1)
println((x map (f map g)) === (x map f map g))

Discipline を用いた法則のチェック

GitHub - typelevel/discipline: Flexible law checking for Scala でlawをチェック出来る

trait FunctorLaws[F[_]] extends InvariantLaws[F] {
  implicit override def F: Functor[F]
 
  def covariantIdentity[A](fa: F[A]): IsEq[F[A]] =
    fa.map(identity) <-> fa
 
  def covariantComposition[A, B, C](fa: F[A], f: A => B, g: B => C): IsEq[F[C]] =
    fa.map(f).map(g) <-> fa.map(f andThen g)
}

import

カスタム演算子はimportしないことも選べる

import cats._, cats.data._, cats.syntax.all._

Day3 型を司るもの, カインド

• Higher-kinded types: 型コンストラクタを受け取る型コンストラクタ
  • 高階関数の型番
• in scala: X[F[A]]

Semigroupal

fmapの写像は1引数, 2引数を移すとどうなる?

Haskell

ex. Just (3 *) と Just 5 で, Just (3 *) の中身を Just 5 に適用したくなったら?
-> Control.Applicative: pure, <*> が定義されている

Applicative

Catsは Applicative を

• Apply
• Applicative
  に分けている

@typeclass trait Semigroupal[F[_]] {
  def product[A, B](fa: F[A], fb: F[B]): F[(A, B)]
}

F[A] と F[B] から effect F[_] に包まれたタプル (A, B) を作る

Cartesian Law

trait CartesianLaws[F[_]] {
  implicit def F: Cartesian[F]
 
  def cartesianAssociativity[A, B, C](fa: F[A], fb: F[B], fc: F[C]): (F[(A, (B, C))], F[((A, B), C)]) =
    (F.product(fa, F.product(fb, fc)), F.product(F.product(fa, fb), fc))
}

Apply

@typeclass(excludeParents = List("ApplyArityFunctions"))
trait Apply[F[_]] extends Functor[F] with Cartesian[F] with ApplyArityFunctions[F] { self =>
  def ap[A, B](ff: F[A => B])(fa: F[A]): F[B]
}

Applicative Style

pure (-) <*> Just 3 <*> Just 5
> Just(-2)

(3.some, 5.some) mapN { _ - _ }
> Some(value = -2)
 
(none[Int], 5.some) mapN { _ - _ }
> None

*>, <*

todo

Haskell Applicative

Just 2 >>= \x -> return (x + 10)
> Just 12
 
(+ 10) <$> Just 2
> Just 12

$ みたいに使える

(+) <$> Just 1 <*> Just 2
> Just 3
 
((+) $ 1) $ 2
> 3
 
-- using monad
Just 1 >>=\x -> (Just 2 >>= \y -> return (x + y))
> Just 3

全てモナド上で計算したい -> 普通の値もモナド値に格上げしたい pure

(+) 1 2
> 3
 
pure (+) <*> Just 1 <*> Just 2
> Just 3
-- pure (+) <*> == (+) <$>
 
Just 1 *> Just 2
> Just 2
 
Just 1 <* Just 2
> Just 1

リストも Applicative のインスタンス

(* 2) <$> [1, 2, 3]
> [2, 4, 6]

Applicative はパーザの開発から派生したものらしい.

• Parsec 3 には Applicative が使われているらしい

Applicative Law

• identity: pure id <*> v == v
• homomorphism: pure f <*> pure x == pure (f x)
• interchange: u <*> pure y == pure ($ y) <*> u
  • この $ どういう意味だ
• fa f == fa <*> pure f

Day4 Semigroup, Monoid

• 同じ問題を解けるならより仮定が少ない方がelegant
• Monoid ならば畳み込みが出来る Foldable
• foldMap: f を適用したものを foldLeft する
  • [true, false, true] foldMap { Conjunction(_) } のようにコンストラクタも使える

Day5 Flatmap, Monad

参考文献

• Haskell 入門