ScalazのKleisliとEndomorphic

Scalazネタです。しかもわりとマニアックな、Scalaz初心者向けではないネタかもしれません。前から書きたかったけど、良いサンプルが思いつかなくて躊躇してましたが、良いサンプルを見つけたのでKleisliとEndomorphicについて書きます。

Kleisliはともかく、Endomorphicは最近入ったので、日本語記事はおろか現時点では英語の解説もほとんど無いのではないかと思います。最近とはこのpull reqですが、7.1.0-M1からで、7.0.x系の最新版の7.0.4には入っていません。*1

さて前置きはこれくらいにして解説を始めます。まず、独習Scalazを引用します。

5日目 騎士の旅

case class KnightPos(c: Int, r: Int) {
  def move: List[KnightPos] =
    for {
      KnightPos(c2, r2) <- List(KnightPos(c + 2, r - 1), KnightPos(c + 2, r + 1),
      KnightPos(c - 2, r - 1), KnightPos(c - 2, r + 1),
      KnightPos(c + 1, r - 2), KnightPos(c + 1, r + 2),
      KnightPos(c - 1, r - 2), KnightPos(c - 1, r + 2)) if (
      ((1 |-> 8) element c2) && ((1 |-> 8) contains r2))
    } yield KnightPos(c2, r2)

  def in3: List[KnightPos] =
    for {
      first <- move
      second <- first.move
      third <- second.move
    } yield third

  def canReachIn3(end: KnightPos): Boolean = in3 contains end
}

コンパクトで、かつ「チェスのナイト*2の動くことが可能な位置を判定する」という、ある程度イメージしやすい意味のある例でいいですね。

今回はこのコードをいじりつつ、解説していきます。


さて、突然ですがScalazは「型クラスによる抽象化を提供するライブラリ」と言っていいと思います。*3ここの5日目のテーマはモナドです。Scalazを使う、使わないにかかわらず、モナドをなんとなく理解しはじめてfor式の使い方がわかってくると楽しいですよね。上記で引用したコード中にも、Listモナドをfor式で扱っている部分があります。


2箇所ありますが、下のdef in3に注目して下さい。以下にその部分だけ抜き出します。

def in3: List[KnightPos] =
  for {
    first <- move
    second <- first.move
    third <- second.move
  } yield third

さて、実はScalazの秘められた力(?)をつかうと、これをまださらに抽象化することができるのです!なっ、なんだってーーー。この記事を読み終わって理解したころには、上記のコードに対しての感想が
「Listモナドに対してfor式をうまく使っていてかっこいい!」
ではなく
「もっと抽象化してかけるのに、なぜこんな書き方をしているのか?」
に変わるかもしれません(?)*4
さて、よく見るとこのコード同じことを繰り返していませんか?3つだとわかりづらいので、例えばこれが7つぐらい連続していたらどうでしょう?変数名も、わざともっと機械的なものにしてみましょう。

def in7: List[KnightPos] =
  for {
    _1 <- move
    _2 <- _1.move
    _3 <- _2.move
    _4 <- _3.move
    _5 <- _4.move
    _6 <- _5.move
    _7 <- _6.move
  } yield _7

同じことの繰り返しですね。さてこれを抽象化するのに使うのがKleisliです。Kleisli自体は、独習Scalazの違う章でも解説されてますね。Kleisliをつかうと、def in3は以下のように書き換えられます。

val moveK: Kleisli[List, KnightPos, KnightPos] = Kleisli(_.move)

def in3: List[KnightPos] =
  (moveK >=> moveK >=> moveK) run this

for式が消えて、Kleisliの合成になりました。for式中にでてきたfirstやsecondといった、それぞれ一度しか使わない変数が消えました。全体の文字数的にはそれほど変わっていません*5が、プログラミングにおいて変数などに名前をつけることは面倒な行為なので「変数名をつけなくて済む」というのはわりと重要なことです。*6



さて、Kleisliを使うことによって一つ抽象化できたわけですが、まださらに抽象化できます。そこで使うのがEndomorphicなわけですが、まずはEndomorphicを使った場合のコードです。

val moveK: Kleisli[List, KnightPos, KnightPos] = Kleisli(_.move)
val moveEndo = moveK.endo

def in3: List[KnightPos] =
  moveEndo.multiply(3).run.run(this)

さて、何が起きているのか順に説明してみましょう。まず、Endomorphicは以下のように定義されていて、

final case class Endomorphic[=>:[_, _], A](run: A =>: A)


「型引数を2つとって、その2つの型引数に同じ型が入るもの」のラッパーです。
何言ってるかわからないですね。たとえば具体的には、Function1[Int, Int]です。
そして今回の場合、moveEndoの型は

Endomorphic[({type λ[α, β] = Kleisli[List, α, β]})#λ, KnightPos]

です。Kleisliは型引数を3つとりますが、「1つめにList型を部分適用*7したもの」に対して、残り2つともKnightPosが当てはめられているので、Kleisli[List, KnightPos, KnightPos]はEndomorphicになります。


さて、わざわざKleisliをEndomorphicというものでラップした意味はなにか?というと、(特定の条件を満たす場合に) *8EndomorphicはSemigroupやMonoidになるということです。というか、SemigroupやMonoidとして使うことが目的なので、そういう使いかたをしない場合は、そもそもEndomorphicでラップしません。


さて、このEndomorphicという名前と、Monoidがでてきた時点で、気づく人がいるかもしれませんが*9以前同じようなものを紹介したことがあります。

ScalazのEndo

ScalazにおいてのEndoとはFunciton1[A, A]をラップしてMonoidとして使えるようにするものでした。
今紹介しているEndomorphicは、Endo自体を抽象化して、"Function1固定"ではなく、"型引数を2つとるもの"に変更したものです。*10



Endoとの関係性を語ったりして、話が少し逸れましたが、コードの解説に戻りましょう。KleisliをラップしてEndomorphicにした場合は、Kleisliの最初の型引数が

  • Bindであれば、Semigroup
  • Monadであれば、Monoid

になります。今回はKleisli[List, KnightPos, KnightPos]で、Listはモナドなので、
Endomorphic[({type λ[α, β] = Kleisli[List, α, β]})#λ, KnightPos]
というもの自体は、Monoidになります。Monoidになるということはつまり、例えばListに入れてfoldMapが使えたりなど、ScalazのMonoidに関する色々な関数がすべて使えるということです。



よって、

moveK >=> moveK >=> moveK

というKleisliの合成は、Endomorphicでラップすれば、単にMonoid*11appendとなり

moveEndo |+| moveEndo |+| moveEndo

と書くことができます。さらに、上記のように「同じものをn回appendする」という操作は最初からMonoidにmultiplyという名前で用意されているので、単に

moveEndo.multiply(3)

と書けるわけです。
こうなったら、def in3def canReachIn3も、「3回動いた位置を判断する」のではなく、「Intを一つ引数にとるメソッド」にしてしまって「n回動いた位置を判断する」ものに簡単に抽象化できるので、そうしてしまいましょう。

val moveK: Kleisli[List, KnightPos, KnightPos] = Kleisli(_.move)

def in(n: Int): List[KnightPos] =
  moveK.endo.multiply(n).run.run(this)

def canReachIn(n: Int, end: KnightPos): Boolean = in(n) contains end


以上でEndomorphicの解説はほぼ終わりです。
実用面で考えると、まぁそれほど多くEndomorphicをうまく使える場面はなさそうだし、あったとしても効率を考えると、関数をKleisliとEndomorphicで2回もラップしてるのでちょっとだけ微妙です。使ったとして抽象化はできてもそれほどコード量が減るとは限らないですしね。そのあたり、ご利用は自己判断で・・・。



最後に余談として、Kleisli以外のEndomorphicの例を出しておきます。

Cokleisli[F, A, A]*12があったときに

  • FがCobindであれば、Cokleisli[F, A, A]をEndomorphicでラップしたものはSemigroup
  • FがComonadであれば、Cokleisli[F, A, A]をEndomorphicでラップしたものはMonoid

になります。
誰かそのCokleisliのEndomorphicのいい例を見つけたら教えて下さい。

*1:なので、以降のコードはScalaz7.1.0-M3で動作確認してます

*2:将棋が分かる人向けに説明すると、桂馬を強化したようなやつ

*3:もちろんそれ以外にも、不変データ構造など色々提供しますが

*4:だからといって、実際にこの程度のものに対して、KleisliやEndomorphicを使うかどうかは微妙かもしれませんが

*5:むしろ増えている?

*6:まぁ実は move.flatMap{_.move.flatMap(_.move)} と書けば変数名付けなくてすみますけどね・・・

*7:値を部分適用するのではなく、"型を"部分適用する、という意味

*8:その部分も丁寧に説明したら長くなりすぎるので、もう省略しますが、条件とはscalaz.Composeとかscalaz.Categoryのことです。

*9:いや、いるのか・・・?

*10:Endomorphicがあれば、Endoはいらないかもしれないが、Endomorphicが後から入った都合もあり、現時点では両方存在している

*11:正確には、appendというメソッド自体はSemigroupから継承したものですが

*12:つまり、F[A] => A という関数のラッパー