Scala
cats

Cats 入門その2(高カインド型)

More than 1 year has passed since last update.


Cats 入門2(高カインド型)

Cats と、 Cats の解説 PDF 「Advanced Scala with Cats」の紹介その2です。

その 1 は こちら です。

今回は 高カインド型の型クラスを中心に紹介していきます。

Functor, Applicative, Monad, Foldable など覚えておくととても役に立つものばかりです。


高カインド型(Higher Kind Type)とは

高カインド型の説明の前に次のコードを見てみます。

val stringList:List[String] = List("A")

var intList:List[Int] = List(1)

上記の stringList と intList は List[A] の A の部分にそれぞれに String と Int という型を与えて、

List[A] から List[String] と List[Int] という型を生成した、という風に考えてみます。

このように考えると List[A] は型を1つパラメータに取って型を生み出すようなものなので、型コンストラクタ (Type Constructor) とも呼ばれたりします。

型にも Int など型パラメータが無いものや List[A] など型パラメータが1つのもの、 Map[K,v] のように2つのものといった種類があります。 この型の種類のことをカインド(類) といいます。

カインドは関数のように型パラメータから型を生み出す式として表現します。

Int など型パラメータの無いものは * と表します。

List[A] は型パラメータ A を関数の引数ととらえて * => * と表します。

Map[K,V] は型パラメータが2つなので * => * => * と表します。

さて関数の中には関数を引数に取る関数や関数を返す関数があり高階関数と呼びます。

それにならうと、高カインド型は類がある型 (List[A]とか Option[A]とか) を型パラメータに取る型を指します。カインドの表現は、 (* => *) => * です。

前の記事では、例えば Monoid で色々な型に結合の手段を提供したように、

型クラスであらゆる型を横断して共通の性質を定義しました。

高カインド型を用いることで List[A] や Option[A] など型パラメータを持つ型に対して型クラスを定義できるようになり、

これらの型に対するプログラムを同じように書くことができます。

高カインド型の宣言は、 class Hoge[F[_]] のように、 F が型パラメータを 1 つ取ることを明示します。

F に具体的な型を与えるには val hoge = new Hoge[List] のように型名だけを与えます。

ここに Int などカインドが異なる型は指定できません。

高カインド型をサポートしている言語は Scala, Haskell など少ないです。

(Java では、ジェネリクスパラメータに上記の F[_] のようなジェネリクスパラメータを持つ型だけを限定するという機能がありません)


また Scala では高カインド型はまだオプション扱いなので import scala.language.higherKinds を書いておかないと警告がでます。


型クラスの紹介

List や Option など型を保持する型に対する有用な型クラスを紹介します。

List[A], Some[A] など値をラップする型のことを以降はコンテナ型と呼びます。

また List(1), Some(1) などのコンテナ型の値をコンテナ値、あるいはコンテナ値の型インスタンスの型の値と呼びます。

例えば List は Functor, Applicative, Monadなどの型クラスのインスタンスなので、

List(1) は Functor 値とか Applicative 値とか Monad 値などと呼びます。


Functor


  • 役割: 1引数関数を、内部に適用する

  • 主なメソッド: map

コレクションや Option でおなじみの map 関数を型クラスとして汎用化したものです。

List, Option, Future などコンテナ型を使うと元の値にそれぞれ、複数の値をまとめる・値が無いかもしれない・非同期計算といった性質を加えることができます。

一方でコンテナ型の内部の値を取り出したり、変更したりすることが難しくなります。

例えば Int に対して 1を加算する関数 (i:Int) => i + 1 を、次のように Int 値に適用するのは簡単です。

val f = (i:Int) => i+1

val n = 1
var n2 = f(1)

一方で Some(1) などの元の値を変更するために上記の関数を適用するのは難しくなりました。

Functor はコンテナ値に対して内部の型に1引数関数を適用する map 関数を提供します。

つまり、 A => B という一引数関数を F[A] という型に適用して F[B] を得ます。

これは lift とも呼ばれていて A=>B を、 F[A] => F[B] という風に、 型 F の世界に持ち上げるような見方もできます。

コレクション・Option・Future など map を備える Scala でおなじみの型は Functor のインスタンスとして汎用化されることになります。

cats ではこれらの型は Functor インスタンスとして定義済みです。

加えて自作の型も Functor のインスタンスにできます。

case class Box[A](value:A)

という型があるとして Box に対する Functor インスタンスは次のように定義します。

implicit val boxFunctor:Functor[Box] = new Functor[Box] {

override def map[A, B](fa: Box[A])(f: (A) => B): Box[B] = Box(f(fa.value))
}

これで色々な型で map 関数が使えるようになります。

List(1,2,3).map(_ * 2) // List(2,4,6)

Box(3).map(_ * 2) // Box(6)

さらに、 Functor[F] を引数・戻り値にすることで Functor インスタンスなら何でも受付可能な関数を作ることができます。

// 内部の値を2乗する関数

def square[F[_]:Functor](functorInstance:F[Int]):F[Int]
= functorInstance.map(i => i * i)

// Functorなら(mapを持つ型なら) 引数に渡せる
square(List(2,3)) // List(4,9)
square(5.some) // Some(25)
square(Box(12)) // Box(144)
val Future = square(Future(23))
Future.onComplete(println) // Future(529)

こういう抽象化は普通の Scala で表現が難しいので、高カインド型の特徴がうまく表れています。


Contravariant


  • 役割: 既存の型クラスのインスタンスを使って、新しいインスタンスを作る。

  • 主なメソッド: contramap

Functor は、 F[A] と、 A => B を使って F[B] を得るものでしたが、

Contravariant は、 F[A] と、 B => A を使って F[B] を得ます。

一見すると意味不明ですが既存の型クラスのインスタンスを使って、新しい型クラスのインスタンスを作る際に役立ちます。

実際私も使いどころを色々考えてみましたが、これしか思いつきませんでした。

説明のため、次の MyShow という型クラスと String の MyShow インスタンスがあるとします。

trait MyShow[A] {

def show(a:A):String
}

implicit val stringShowInstance: MyShow[String] = new MyShow[String] {
override def show(a: String): String = a
}

Contravariant は 型クラスに対してインスタンスを作ります。

implicit  val myShowContravariant:Contravariant[MyShow] = new Contravariant[MyShow] {

override def contramap[A, B](fa: MyShow[A])(f: (B) => A): MyShow[B] = new MyShow[B] {
override def show(b:B):String = fa.show(f(b))
}
}

こうすると stringShowInstance を使用して新しい MyShowのインスタンスを contramap の呼び出しだけで作成することができます。

例えば Boolean 型に対しては、次のように Boolean => String のマッピングを定義すればインスタンスを作成できます。

implicit val booleanMyShowIntanse:MyShow[Boolean] =

Contravariant[MyShow].contramap(stringShowInstance)((b:Boolean) => b.toString)

適当な自作型に対しても適用できます。

case class Box(value:String)

implicit val booleanMyShowIntanse:MyShow[Box]
= Contravariant[MyShow].contramap(stringShowInstance)((b:Box) => "Box(" + b.value + ")")

Contravariant を使うと基本的な型クラスのインスタンスから、徐々に複雑なインスタンスを作ることができそうです。

実際、PDF にも JSON ライブラリで使うと記述してあり Contravariant を使いこなせば、

任意の case class から JSON の変換の定義を導出できる可能性があります。


Invariant


  • 役割: 既存のインスタンスの振る舞いを変える

  • 主なメソッド: imap

Contravariant に名前が似ていますが機能も Contravariant に追加したような感じです。

B => A の関数で型を変化させた後 A => B で元の型に戻します。

Semigroup は Invariant のインスタンスにもなっていますので、これを使って

Semigroup[String] の combine の振る舞いを変更してみます。

通常、文字列の combine の振る舞いは文字列の連結になります。

import cats.syntax.semigroup._

import cats.instances.string_
"123" |+| "456" // "123456"

上記の代わりにSemigroup[Int] を使って Semigroup[String] インスタンスを作ってみます。

import cats.syntax.semigroup._

import cats.Semigroup
import cats.instances.invariant._
import cats.instances.int._

implicit val stringToIntSemigroup: Semigroup[String] =
Semigroup[Int].imap((i: Int) => i.toString)((s: String) => s.toInt)

"123" |+| "456" // "579"

これは文字列の |+| 呼び出しに対して、imap の第二引数の s.toInt を使って 123 |+| 456 の呼び出しに変換しその結果 579 を imap の第一引数の i.toString で "579" に変換していることになります。

これもあまり表だって使うことはなくライブラリ作成者向けの機能かなと思います。


Apply, Applicative


  • 役割: N 個のアプリカティブ値への N 引数関数適用

  • 主な型クラスのメソッド:


    • Apply :ap, product,

    • Applicative: pure



  • 主なsynatx: tuppled, mapN, pure


PDF版の cats 0.9 と今回取りあげている cats 1.0 系で Syntax のAPIが特に変わった部分です。

0.9系では |@| という中置演算子の syntax がありましたが 1.0 では非推奨となり、替わりに mapN, tupled を使うようになりました。



Apply

Functor を使うと1つの Functor値、F[A] について map で一引数を適用して、 F[B] を作ることができました。

Apply は Functor を拡張し N 個の Functor 値に N 引数関数を適用することができます。

Apply の型クラスの主要なメソッドは def product[A, B](fa: F[A], fb: F[B]): F[(A, B)]

これを使うと 2つの Apply 値を1つにまとめることができます。

product を再帰的に適用することで N 個の Apply 値を1つにまとめることができます。

なお、product Apply の上位 trait の Semigroupal で定義されているメソッドですが

Apply では product の代わりにより汎用的な def ap[A, B](ff: F[A => B])(fa: F[A]): F[B] を定義することで、

product を導出するようになっています。

Apply の Syntax を使うとタプルに対して tupled, mapN などのメソッドが呼び出せます。

tupled は Apply 値をまとめて1つのタプルにします。

mapN はApply 内部の値を引数にして、関数適用を行います。

(1.some, 2.some).tupled // Some((1,2))

(1.some, 2.some).mapN(_ + _) // Some(3)
(1.some, 2.some, 3.some).mapN(_ * _ * _) // Some(6)

Apply 値のインスタンスの種類に応じて、結果が変わるのが面白いところです。

Option の場合 None がどこかにあれば、結果は None になります。

def check(i:Int):Option[Int] = if (i % 2 == 1) Some(1) else None

(check(1), check(2)).mapN(_ + _) // None
(check(3), check(5)).mapN(_ + _) // Some(8)

List の場合 List の各要素の組み合わせができあがります。

(List(1,2), List(3,4)).tupled // List((1,3), (1,4), (2,3), (2,4))

Future の場合、複数の Future が並列で計算されて、その結果を合成するように振る舞います。

import scala.concurrent.{Await, Future}

import scala.concurrent.ExecutionContext.Implicits.global
import scala.concurrent.duration._

def take500ms(n:Int):Future[Int] = Future{
println("start in " + Thread.currentThread())
Thread.sleep(500L)
println("end in " + Thread.currentThread())
n
}
// 下記3つの Future は並列で動く。
val a = (take500ms(8), take500ms(12), take500ms(22)).mapN(_ + _ + _) // Future(42)

a.onComplete(println) // 42
Await.ready(a, 1.seconds)


Applicative

Applicative は Apply を継承し pureメソッド( A => F[A] ) を追加しています。

pure を使うと普通の値を Applicative 値に変換できるので、

普通の値を Applicative 値にして他の Applicative 値(またはApply 値) と mapN などの演算で合成できるようになります。

Applicative のインスタンスであれば pure の呼び出しで各 Applicative 値に変換できるようになります。

1.pure[Option] // Some(1)

1.pure[List] // List(1)

pure は、コンストラクタの抽象化をしているような感じです。

そのため、Applicative 値と、Applicative でない値を混在した関数を作ることができます。

/** a を fa の内部に追加するサンプル関数 */

def addA[F[_]:Applicative, A](a:A, fa:F[A])(f:(A,A) => A ):F[A]
= (a.pure[F], fa).mapN(f) // aを、Applicativeに昇格させて、mapN でまとめる。

addA(3, List(1,3,4))(_ + _) // List(4,6,7)
addA(3, 4.some)(_ * _) // Some(12)

後で紹介する Foldable や Traverble の内部でも使われています。

これは pure によって、コンテナ型に対して畳込み演算ができるためです。


Monad


  • 役割: モナド値の逐次計算・関数合成

  • 主な型クラスのメソッド: unit, flatMap

  • 主なsynatx: flatMap, >>=

Applicative で、複数のコンテナ値を扱うことができるようになりましたが、

実は、前のコンテナ値に依存するような処理を書くことはできません。

Map から1つ値を取り値が取れたらその値をキーにしてもう一度 Map から値を取る例を考えてみます。

val map = Map(1 -> 2, 2 -> 3, 3 -> 4)

def get(i:Int):Option[Int] = map.get(i)

Scala ではこの場合に flatMap や for 式で書くことができます。

for式は、flatMap の糖衣構文です。

def twice(i:Int) = get(i).flatMap(n => get(n))

// ↑と同じ処理を、for で書ける。
def wtice2(i:Int) = for(n <- get(i); a <- get(n))yield a

twice(1) // Somw(3)
twice2(3) // None

flatMap や for 式の最初の式で取得した値 n が最初のコンテナ値の内部の値で、

その値を使って次のコンテナ値を取得するということができています。

こういう処理は Applicative では実現できません。Applicative は独立した要素の計算結果を最終的にまとめるためです。

Scala では flatMap, map, filter を定義している型を暗黙的に Monad とみなして for 式で呼び出すことができるようになっていますが、

cats の Monad はその仕組みを高カインド型として整理したものになります。

Monad が実現するのは複数 の Monad 値が前後関係に従って処理を逐次的に処理していくことなので、この性質を文脈依存とか呼ぶこともあります。

プログラムの観点では A => F[B] という値からコンテナ値を生み出す関数を flatMap で連鎖していくことにななるので、コンテナ型に逐次計算・手続き型の処理を持ち込むことになります。

A => F[B] の関数を何度もつなげているので関数合成ととらえてもいいと思います。

例えば、Future の呼び出しも flatMap で連鎖させることで逐次処理になります。

def hogeFuture(a:Int):Future[Int] = ...

for(
n <- hogeFuture(3); // この Futureの計算が終わってから、
a <- hogeFuture(n) // こちらが呼ばれる。
)yield a

上記の処理は最初の非同期計算の結果を、次の計算で使うので逐次処理でなければなりません。

ただし flatMap は前のモナド値の結果を使う必要はないため、次のような文脈依存でない処理も記述できます。

for(

a <- hogeFuture(3); // 2つの処理に依存関係はないが逐次実行になる。
b <- hogeFuture(4)
)yield (a + b)

これを Future と for 式の落とし穴として紹介されることがありますが、

これは良い悪いではなく、 Monad の性質に従うとそうなるとしか言えません。

並列に処理をさせたい場合や文脈依存でなくても問題ない場合は、 Applicative で計算する方が適切かもしれません。

// これは並列で動く

(hogeFuture(3), hogeFuture(4)).mapN(_ + _)

List, Option, Either, Future などよく使う型は、大体 Functor, Applicative, Monad のインスタンスです。


Foldable


  • 役割: コンテナ値の畳込み演算

  • 主な型クラスのメソッド: foldRight, foldLeft, combineAll

  • 主な synatx: foldRight, foldLeft 他多数

コンテナ値に対する畳込み演算を行います。

コレクションには最初からfoldLeftなどのメソッドがありますが、それを Foldable 型クラスで汎用化したものと言えます。

Foldable には fold 系のほかに派生した多くのメソッドがあるので、一度目を通しておくといいと思います。

// syntax

List(1,2,3).foldLeft(0)(_+_) //6

// インスタンス
Foldable[List].foldLeft(List(1,2,3), 0)(_+_) // 6

// 畳込み演算の亜種として、条件判定を行うものもある。
Foldable[List].exists(List(1,2,3))(_ % 2 == 0) // true. 条件を満たすものが1つでもあるか
Foldable[List].forall(List(1,2,3))(_ < 4) // true // すべての要素が条件を満たすか

combineAll はコンテナ型の内部の型が、Monoid である場合のみ使用でき、

Monoid の単位元と結合を使って、畳込みを行います。

// int は、 Monoidのインスタンス

List(1,2,3).combineAll //6

foldMap はコンテナ内の値に map を適用してから fold するもので、こちらも map 後の値が Monoid である必要があります。

List(1, 2, 3).foldMap(_.toString) // "123"

SortedMap と組み合わせると同一キーでグルーピングとかが簡単にできて面白いです。

(Map ではなくSortedMap のみが Foldableの対象です。)

case class Score(subject:Int, score:Int)

val scores = List(Score(1, 100), Score(2, 30),Score(2, 40),Score(3, 10),Score(3, 60))

// Listの各要素を SortedMap(Int, List) にして、Monoidで結合すると同一キーの値が List結合されてグルーピングされる
val scoresPerSubject = scores.foldMap(s => SortedMap(s.subject -> List(s.score)))
// Map(1 -> List(100), 2 -> List(30, 40), 3 -> List(10, 60))

他にも末尾に M がついたメソッドは畳込み先の型をモナド値にします。

例えば、 fold で畳込みをするが値によっては畳込みをやめたい場合は foldM を使って Option 値に畳込みを行います。

// 0じゃない場合だけ積算する

def productNonZero(acc:Int, b:Int) = if (b != 0) Some(acc * b) else None

val s1 = List(1, 0, -3).foldM(1)(productNonZero) // None
val s2 = List(1, 2, -3).foldM(1)(productNonZero) // Some(-6)

API には foldK などがあり、高カインド型に対する畳込み演算もありそうな雰囲気ですが一旦この辺でやめておきます。


Foldable の使い方を覚えると色々と応用が利きそうです。


Traversable


  • 役割: コンテナ値の走査

  • 主なsynatx: traverse, sequence

Traversable は、ネストした コンテナ値に対して有用な操作を提供します。

Foldable はコンテナ値を走査した後畳みこんだ結果を再生しますが、

Traversable はコンテナ値を走査して何らかの処理を行うまでにとどめてコンテナ値の構造をそのまま保ちます。

よくあるパターンが、 List[Option] や List[Future] など複数のコンテナ値をまとめて扱うものです。

Scala 標準の Future には Future.sequence というメソッドがあり、

これを使うと複数の Future である Seq[Future] を、 Future[Seq] に変換できます。

Traverse はこれをコンテナ型全般に一般化したものです。

// 一行ごとに文字があるかを調べる

def isNotEmpty(line:String):Option[String] = if (line.length > 0) Some(line) else None

val lines = List("one", "two", "three")

// 一行ごとにチェックをする
val checkedLines:List[Option[String]] = lines.map(isNotEmpty) // List(Some("one"), Some("two"), Some("three"))

上記ですべての要素のチェックが成功していたら処理を続けたい場合に、 Traversable の sequence が使えます。

sequence を使うと F[G[A]] を G[F[A]] のようにネストしたコンテナを逆にすることができます。

val result:Option[List[String]] = checkedLines.sequence // Some(List("one", "two", "three"))

List[Option] から Option[List] へ入れ替わり元々あった List の要素が保たれていますので、

この内容をチェックが正常に終わった結果として次の処理へ使うことができます。

traverse は sequence の一般的な形式で、 F[A] と、 A => G[B] の関数を取って、G[F[B]] を生成します。

前述の例を今度は失敗する入力例で traverse で実現してみます。

val lines = List("one", "", "three")

val result:Option[List[String]] = lines.traverse(isNotEmpty) // None

便利 そして 便利。


まとめ

高カインド型の有用な型クラスを紹介しました。

モナドが有名ですが、 Applicative や Foldable も便利です。

なお Cats の組み込みの型クラスの紹介が中心にしたので触れませんでしたが、


型クラスのインスタンスを作る際には型クラスごとに 法則 (Law) を守る必要があります。

例えば Monoid 則は次のようなものです。



  • (a |+| b) |+| c == a |+| (b |+| C) - 結合順序を変えても結果が同じ


  • Monoid.empty |+| x = x - 単位元 と x の結合は、x に等しい


  • x |+| Monoid.empty = x - x と 単位元 の結合は、x に等しい

この法則を守らずに実装すると思わぬ結果が生まれますので注意しましょう。

各型の法則などは、ネット上や cats のドキュメントを参照してください。

また Law を守っているかチェックするライブラリもあります。

次回は Cats のデータ型について紹介します。