はじめるコモナド -- モナドの双対を使って一定のルールでリストの内容を結合する

HaskellやScalaで関数型プログラミングをしていると、コなんとかというやつに出くわすことがある。でもコなんとかからのアプローチは決まってそっけない。深夜にやってる映画を見せまいとする親のようだ。まだ君には早いよ、そのうちね、といった具合に。ここで一つ大人になろうじゃないか。といってもここでは初歩的な話しかしないのでどうぞご安心を。

まず言っておこう。コはCo、すなわち数学語で言うところの双対という意味で、圏論的に双子のような関係にある存在のことを表している。日常会話でもコファウンダーとかコオーサーとかココイチとか言うよね。最後のは嘘だけど・・・

圏論的な双対ってのは、圏論の道具である可換図を使って何か(モナドでもタプルでもなんでもいい)を表現したとき、矢印を全部逆にして得られるもののことだ。まぁ双子だってことだけ覚えておけばいい。

Monadの双対: Co-monad
Freeの双対: Co-free

これらの双対は、元の概念とは逆の作用を保持していることが多い。今回はそんな双対シリーズの中でもMonadの双対であるComonadについて触れ、その応用を紹介する。

Comonad

Comonadとは、以下の型クラスで表現されるようなものである:

def coflatMap[A, B](fa: F[A])(f: (F[A]) => B): F[B] // extractを用いて実装できる
def extract[A](x: F[A]): A // coflatMapを用いて実装できる

これに加えて、ComonadはFunctorでもあるのでmapの実装も必要だ。モナド則と同じように一定のコモナド則を守る必要もある。今回は既にコモナドであることが分かっている物を使うだけだから、そのへんの説明はここでは省略する。

いったんMonad

いったんMonadの話をしよう。厳格な話を無視しておおまかな事を言うと、まずMonadが構造の縮約のような役割を果たす。例えば、Free MonadをfoldMapして潰していったりとか、flattenを使ってSome(Some(42))を潰してSome(42)にするといった具合だ。これにより、例えばListを処理して要素あたりいくつものListが生成されるけれど、最後はすっかり元のListに吸収される、といった処理を書ける:

import cats.data.NonEmptyList
import cats.implicits._

val lis: NonEmptyList[String] = NonEmptyList.of("abc*def", "ghi*jkl")

val Split = """(.*)\*(.*)""".r.anchored
lis.flatMap(s =>
  s match {
    case Split(x, y) => NonEmptyList.of(x, y)
  }
)

この実行結果はNonEmptyList("abc", "def", "ghi", "jkl")になる。特定のトークンで文字列が分割され、flatMapの効果でこれが外側のNonEmptyListに吸収されたのだ。

flatMapのシグネチャにも、この性質が浮き彫りになっている:

def flatMap[A, B](fa: F[A])(f: A => F[B]): F[B]

このシグネチャは、モナドF[A]に対して、A => F[B]を適用しても、最終的にはF[F[B]]ではなくF[B]にできなければならない、ということを意味している。このような性質を持つ構造は沢山あり、またそれを使って強力な演算を安全に行えるがゆえに、Monadは愛用されている。

coflatMapのシグネチャ

さて、Comonadが持つcoflatMap(そう、flatMapの双対だ)とextractのシグネチャを見てみよう:

def coflatMap[A, B](fa: F[A])(f: (F[A]) => B): F[B]
def extract[A](x: F[A]): A

ちょうどfの構造が逆になっていることに気が付くだろうか？

flatMap
- f: A => F[B] -- fは構造を生成するので、Monadがこれを潰す
coflatMap
- f: F[A] => B -- fは与えられた構造を消費するので、Comonadがこれを再包装する

これは何を意味しているのだろう？もちろんMonadもComonadも抽象的な部品なので、このシグネチャに合致するような解釈をいくつでも与えることができる。コモナドF[A]に対して、F[A] => Bを適用しても、最終的にはBではなくF[B]にできなければならない。そのような構造とは何か？

ここでは、先述したモナドの役割を逆転させて、Comonadは構造の生成・展開のような役割を果たす、と考えてみよう。この解釈に合致するような振舞いをするComonadのインスタンスとして、次のようなものが存在する:

NonEmptyList
Tuple

Monadであるような構造が必ずComonadであるとは限らない。例えばNonEmptyListはMonadでありComonadでもあるが、OptionやListはComonadにならない。extractのシグネチャは、常に F[A]からAが取り出せることを要請しているからだ。要素が存在しないかもしれないOptionやListでは、この期待に応えることは難しい。NonEmptyListやTupleにはこれが可能だ。

NonEmptyList

NonEmptyListを例に、具体的にcoflatMapがどう振る舞うか見てみよう。試しにidentityを渡して、どのような値がfに渡ってくるかを見てみよう:

val ints: NonEmptyList[Int] = NonEmptyList.of(42, 43, 44)
ints.coflatMap(identity)
// => NonEmptyList(NonEmptyList(42, 43, 44), NonEmptyList(43, 44), NonEmptyList(44))

再帰的にtailを取り出したような挙動になった。確かにこれはcoflatMapのシグネチャとも合致している。

ちなみに、extractの挙動は単なるheadだ:

ints.extract // => 42

特定のトークンが来たときにリストを結合する

冒頭のMonadを使った例では、特定のトークンが来たときに文字列を分割し、最終的に1本のListを構成していた。NonEmptyList("abc*def", "ghi*jkl")が最終的にはNonEmptyList("abc", "def", "ghi", "jkl")に変形されたのだ。

では、逆に特定のトークンが来たときに文字列を結合するという処理は可能だろうか？少なくとも、Monadでは不可能だ。

このような処理はComonadの十八番だ。例として、"*"文字がやってきたら直近2つの文字列を結合することにしてしまおう。

入力: NonEmptyList("abc", "def", "*", "ghi", "jkl", "*", "mno", "pqr")
出力: NonEmptyList("abcdef", "ghijkl", "mno", "pqr")

以下のようなコードを書ける:

val lis3: NonEmptyList[String] =
  NonEmptyList.of("abc", "def", "*", "ghi", "jkl", "*", "mno", "pqr")

lis3.coflatMap {
  case NonEmptyList(x, y :: "*" :: _) => Some(x ++ y)
  case NonEmptyList(_, "*" :: _)      => None
  case NonEmptyList("*", _)           => None
  case NonEmptyList(x, _)             => Some(x)
}.toList.flatten
// => List("abcdef", "ghijkl", "mno", "pqr")