モナド

※以下は間違いの可能性があるので信用しないように。これは単なる学習メモです。

第一印象

モナドとは、連続して計算を行うパイプラインを簡単に作成するためのものである。古今東西同様の仕組みはいろいろ考えられてきたが、その一種と言える。例えば、

unixのパイプ
入力を受け取ってフィルタリングを行い出力をするコマンドをつなぎ合わせる。

ls -l | grep something |  sort -k 6,6

Javaのストリーム
これも同じ。前のオブジェクトの入力を受け取り、フィルタリングを行う出力するオブジェクトを数珠つなぎにする。

 BufferedReader r = new BufferedReader(new InputStreamReader(new FileInputStream("something")));

形態は異なるけれどもやりたいことはこれと同じ。「任意の計算をつなぎあわせて所望の目的が達成できればとても便利だろう」という悲願の実現であると言える。

モナド則

「モナド」となるオブジェクトは「モナド則」を満たす必要があるという。モナド則とは以下のようなものだ。

(1) m flatMap unit ≡ m
(2) unit(x) flatMap f ≡ f(x)
(3) m flatMap g flatMap f ≡ m flatMap {x => g(x) flatMap f}

関数脳のつくり方　Second Season　～モナドで悟りをひらく～より

Haskellの本にも同じような記述がある（上と合うように順序を並べ替えてある）。

2. m >>= return == m
1. (return x) >>= f == f x
3. (m >>= f) >>= g == m >>= (\x -> f x >>= g)

「ふつうのHaskellプログラミング」（Softbank Creative)より

※ちなみに、先の「関数脳のつくり方」に「それらのメソッド(filter,map,flatMap)があったうえで，「モナド則」を満たす必要があります」とあるが、これは間違いではないだろうか？たしかに書籍「Scalaスケーラブルプログラミング」P438にも「あらゆるモナドは、map、flatMap、filterの３つ、さらに「ユニット」コンストラクターによって特徴づけられる」とあるが、少なくともこれらは厳密なモナドの定義とは無関係のようである。

Listがモナド則を満たすかを確認する

Listがこのとおりに動作するかを確認してみる。

val m = List(1, 2, 3)
def unit = (x: Int) => List(x)
def f = (x: Int) => List(x * 3)
def g = (x: Int) => List(x / 2)

※もちろんすべてのf,gについて確かめることは不可能なので、少なくともf,gの適用順序が変わると結果が変わるようにしとく。

※unitというのは、単なるコンストラクタ呼び出し（ほんとはコンストラクタではないのだが）。

すると、(1)は

m flatMap unit // List(1, 2, 3)になる

(2)は

unit(33) flatMap f // List(99)になる。
f(33)              // List(99)になる。

(3)は

m flatMap g flatMap f  　　　　　　　　　// List(0, 3, 3)になる。
m flatMap {x => g(x) flatMap f}  // List(0, 3, 3)になる

と、とりあえず一種類の関数についてListがモナド則を満たすことは確認できた。

モナド則の意味

さて、モナド則は何を意味しているのだろうか？日本語で説明して欲しいものである。上のListの例に即して考えてみる。

(1) m flatMap unit ≡ m

これは簡単。Listのそれぞれの要素にコンストラクタを適用し、要素を一つだけ持つListを生成しても、それらはListから取り出され合体されて元通りListになる、ということである。

(2) unit(x) flatMap f ≡ f(x)

これも簡単。xを引数としてunitでモナドを作り、そのflatMapが動作するとき、fに与えられる引数はxである、ということ（たぶん）。

(3) m flatMap g flatMap f ≡ m flatMap {x => g(x) flatMap f}

これは結合則のようなものと思われる。左辺はListに対してflatMap gを適用した結果にflatMap fを適用しているが、右辺では、個別の要素にgを適用した結果にflatMap fを適用する、という処理をListに適用している。

やはりよくわからないが、しかしこれらのモナド則に反する例を考えてみれば理解を深めることができるのではないか。しかし、ちょっと考えてみれば、これらに反する例はむしろ「不自然」と言えるので、素直に実装すればモナド則に反することは無いような気がする。どうみても不自然でモナド則に反する例は以下のとおり、

unitが引数を無視して無関係なものを返す。
flatMapが引数の関数を呼び出した結果を無視したりデタラメに並び替える。

モナドを実装してみる

考えていてもわからないので、とりあえずモナドを実装してみる。インチキだが、簡単のため、以下のようなコードをでっち上げる。内部ではListを使っているが、当然ながら外側からはそれはわからない。

case class MyList[T](x: T*) {
  val list: List[T] = x.toList

  def flatMap(f: (T) => MyList[T]): MyList[T] = {
    def fResultToList(x: T): List[T] = {
      val fResult: MyList[T] = f(x)
      fResult.list
    }
    val newList: List[T] = list.flatMap(fResultToList)
    MyList(newList: _*) // 注：これはListを可変長引数に変換している。
  }

  override def toString(): String = {
    list.map(_.toString()).mkString(" ")
  }
}

これを以下のように呼び出す。

    val m = new MyList(1, 2, 3)
    println(m)

    def unit = (x: Int) => MyList(x)
    def f = (x: Int) => MyList(x * 3)
    def g = (x: Int) => MyList(x / 2)

    println(m flatMap unit)
    println(unit(33) flatMap f)
    println(f(33))
    println(m flatMap g flatMap f)
    println(m flatMap {x => g(x) flatMap f})

結果は以下のようになり、リストモナドの完成である（たぶん）。

ここまでの「推測」が間違っていなければ、モナドとは非常に単純なものであることがわかる。おそらく、この単純なものを使って、難しいことをやろうとするから難しくなってしまうのだろう。モナドを説明するサイトがいくつもあるが、例が難しすぎて（あるいはややこしすぎて）途中で面倒になってしまう。

Javaでモナド実装

これをJavaで無理やり実装してみる。ジェネリックスをもサポートしようとすると、かなり大変であることがわかる。モナド自体の実装は大したことはないのだが、関数の代わりに匿名オブジェクトを作成しなければならない点がかなりめんどい。わかりきったことをうだうだと書かなければならないので。

※ちなみに、だからといってスクリプト言語信者がJavaを批判するのは完全に間違い。いちいち型を書かなければならない代わりに、それらの言語には決して存在しようもない「安全性」が得られるのである。これらは言語の優劣ではなく、単純に何を重要視するかの問題でしかない。また、多くのスクリプト言語においてこのような安全性を求めるなら、かなり多くのユニットテストを記述しなければならないうえ（おそらくこのコードよりも大きくなるだろう）、それらは決してコンパイラによる機械的に検出可能な範囲には及ばない。

interface Function1<A1, R> {
  public R doit(A1 a1);
}

class OurList<T> {

  private java.util.List<T>list;
  
  public OurList(T...args) {
    list = java.util.Arrays.asList(args);
  }
  protected OurList(java.util.List<T>list) {
    this.list = list;
  }

  public OurList<T>flatMap(Function1<T, OurList<T>> func) {
    java.util.List<T>resultList = new ArrayList<T>();
    for (T element: list) {
      OurList<T>newList = func.doit(element);
      resultList.addAll(newList.list);
    }
    return new OurList<T>(resultList);
  }

  @Override
  public String toString() {
    StringBuffer result = new StringBuffer();
    for (T e: list) {
      result.append(e.toString() + " ");
    }
    return result.toString();
  }
}

interface OurListFunc extends Function1<Integer, OurList<Integer>> {
}

public class MonadTest {
  public static void main(String[]args) {
    OurList<Integer> m = new OurList<Integer>(1, 2, 3);
    System.out.println(m);

    OurListFunc unit = new OurListFunc() {
      public OurList<Integer> doit(Integer x) {
        return new OurList<Integer>(x);
      }
    };
    final OurListFunc f = new OurListFunc() {
      public OurList<Integer> doit(Integer x) {
        return new OurList<Integer>(x * 3);
      }
    };
    final OurListFunc g = new OurListFunc() {
      public OurList<Integer> doit(Integer x) {
        return new OurList<Integer>(x / 2);
      }
    };
    
    System.out.println(m.flatMap(unit));
    System.out.println(unit.doit(33).flatMap(f));
    System.out.println(f.doit(33));
    System.out.println(m.flatMap(g).flatMap(f));
    
    OurListFunc h = new OurListFunc() {
      public OurList<Integer> doit(Integer a) {
        return g.doit(a).flatMap(f);
      }
    };
    System.out.println(m.flatMap(h));
  }
}

実行結果は当然以下

Option

さて、少なくとも私の理解が正しいのであれば、モナドとは何であるかが理解できたし、モナドの記述も極めて簡単であることがわかった。「この仕組みを使うと何がどのように便利になるのか」を知りたいところである。次はScalaに組み込みのOptionを見てみる。これもモナドだという。

ただし、単純にunit(コンストラクタ）やflatMapを使っただけでは、「ありがたみ」は全くない。最初に書いたように、それらを連続して使う、つまり計算をつなぎ合わせるところにモナドのありがたみがある、と予測している。

まず、ScalaのOptionのソースコードから関係ありそうな部分を抜き出すと以下になる。日本語のコメントをつけてみた。

object Option {
  /** これがunit。Option(a)などと呼び出すのだが、aがnullであればNoneが返される */
  def apply[A](x: A): Option[A] = if (x == null) None else Some(x)
}

sealed abstract class Option[+A] extends Product with Serializable {
  /** SomeかNoneかを判断するだけ */
  def isEmpty: Boolean

  /** 中身を返す。Noneであれば例外 */
  def get: A
  
  /** これがflatMap。自身がNoneであればfは呼び出さずにNoneを返す */
  def flatMap[B](f: A => Option[B]): Option[B] = 
    if (isEmpty) None else f(this.get)
}

/** 値を一個だけくるむコンテナ。これはケースクラスなのでapplyが自動的に定義されていることに注意 */
final case class Some[+A](x: A) extends Option[A] {
  def isEmpty = false
  def get = x
}

/** 何も持たないコンテナ */
case object None extends Option[Nothing] {
  def isEmpty = true
  def get = throw new NoSuchElementException("None.get")
}

※applyについてはメソッド呼び出しのように見えるものを参照のこと。

Optionの用例については関数脳のつくり方　Second Season　～モナドで悟りをひらく～を参照のこと。

wikipediaの説明

ここでwikipedia(英語版2011/5/28時点)のmonadの説明を読んでみる。

Monad (functional programming)

In functional programming, a monad is a programming structure that represents computations. Monads are a kind of abstract data type constructor that encapsulate program logic instead of data in the domain model. A defined monad allows the programmer to chain actions together to build a pipeline to process data in various steps, in which each action is decorated with additional processing rules provided by the monad. Programs written in functional style can make use of monads to structure procedures that include sequenced operations,[1][2] or to define some arbitrary control flows (like handling concurrency, continuations, side effects such as input/output, or exceptions).

関数型プログラミングにおいて、モナドとは計算を表現するプログラミング構造である。モナドは、ドメインモデルにおけるデータの代わりに、プログラムロジックをカプセル化する抽象的なデータタイプコンストラクタの一種である。定義済みモナドは、アクションをつなぐことによって様々な段階におけるデータ処理のパイプライン作成を可能にするものであり、それぞれのアクションにおいてはモナドによって提供される付加的な処理が追加される。関数スタイルで記述されたプログラムは次のような構造的処理にモナドを利用することができる。つまり、逐次的処理、抽象的なコントロールフロー（並列性のハンドリング、継続的処理、I/Oのような副作用や例外）。

Formally, a monad is constructed by defining two operations (bind and return) and a type constructor M that must fulfill several properties to allow the correct composition of monadic functions (i.e. functions that use values from the monad as their arguments).

形式的には、モナドはbindとreturnという二つの操作とモナディック関数の正しい構築を行うための様々なプロパティを提供する型コンストラクタＭからなる。モナディック関数とは、モナドからの値をその引数としてとるものである。

The return operation takes a value from a plain type and puts it into a monadic container of type M. The bind operation performs the reverse process, extracting the original value from the container and passing it to the associated next function in the pipeline.

return操作はプレーンタイプの一つの値をとり、それをモナディックコンテナMに格納するものである（訳注：returnはHaskellの用語。これまで出てきた用語ではunitにあたる）。 bind操作は、それとは逆の操作で、コンテナからオリジナルの値を抽出して、それをパイプライン中の次の関数に引き渡すものである（無論これはflatMapのこと）。

A programmer will compose monadic functions to define a data-processing pipeline. The monad acts as a framework, as it's a reusable behavior that decides the order in which the specific monadic functions in the pipeline are called, and manages all the undercover work required by the computation.[3] The bind and return operators interleaved in the pipeline will be executed after each monadic function returns control, and will take care of the particular aspects handled by the monad.

プログラマはモナディックな関数をデータ処理パイプラインとして構成するだろう。モナドはフレームワークとして振舞うが、それは計算の水面下で必要な順序を決定する再利用可能な振る舞いである（うーん、ちょっと違うかも）。 bindおよびreturnオペレータはパイプライン中に配置され、それぞれのモナディック関数が制御を戻した後に実行される。そして、そのモナドによって扱われる特別な側面を実現するのである。

かなりわかりづらいが、だいたいのところはわかる。最初の例で言えば、 linuxでのパイプ

ls -l | grep something |  sort -k 6,6

の「|」がモナドであり、間に挟まっているコマンドがモナディック関数である。

IOモナド

さて、IOモナドである。これが問題なのである。 Scalaでは関係ない（IOモナドを使う必要はまったくない）のだが、純粋関数型言語（副作用をもたない）であるHaskellではこいつの力を借りないと、println("Hello, World")さえできないそうなのである。

ところがいきなりこれが難しい。なぜかといえば、副作用を実現できない言語で副作用を実現するという禅問答みたいなことが行われるそうなのである。モナドが何であって、何でないかがわかれば、「そんなことはありえない」ことくらいすぐわかるというものだ。

IOモナドを説明するあらゆるサイトは話しを難しくしているだけであって、とても他人に理解させようという気はないらしい。それに異を唱えているのが以下の方である。これはとてもわかりやすい（それでも難しいのだが）。

サンプル

JavaプログラマのためのIOモナドを参考にしてScalaで記述してみた。単に入力された一行を出力するだけだが、原理を理解していないのでこれで良いのかはわからない。

import java.util.Scanner
object IOMain {

  abstract trait IO[A] {
    def perform: A
    def flatMap[B](func: (A) => IO[B]): IO[B] =  new IOAction(this, func);
  }

  class IOAction[A, B](a: IO[A], func: (A) => IO[B]) extends IO[B] {
    def perform: B = func(a.perform).perform;
  }

  object GetLine extends IO[String] {
    val scanner: Scanner = new Scanner(System.in)
    def perform = scanner.nextLine
  }

  class PutStr(str: String) extends IO[Unit] {
    def perform { print(str); }
  }
  
  def main(args: Array[String]) {
    val main =
      new PutStr("please input string: ").flatMap(
        (Unit) => GetLine.flatMap((line: String) => new PutStr(line + "\n"))
      )
    main.perform // 処理系
  }
}

。。。というか、これではモナド則を満たしていないような気がする。後で書きなおそう。

ともあれ、ここでのポイントは以下

純粋関数型言語ではユーザプログラム側で副作用を起こすことはできない。それらは処理系が担うもの。
だから、上のperformというメソッドはユーザプログラム側で呼び出してはいけない。それらの呼び出しによってのみ副作用が起こる。
実際のHaskell等では、例えばPutStr.perform（に相当するもの）が上のように副作用を起こすものになっているのか、あるいは「単なるIO指示書」になっているのか不明だが、ユーザプログラム側にとってはどちらでも構わない。結局それを直接呼び出すことはできないのだから。

これを使った最も簡単なプログラムは以下。

val main = new PutStr("Hello, World\n");
main.perform // 処理系

連続して二つ出力するのは以下。

val main = new PutStr("hello, ").flatMap((Unit) => new PutStr("world"))
main.perform // 処理系

サンプル２

書き換えてみた。型パラメータを使うのは私の力では無理のようなのでStringに限定。 flatMapという名前はいかにも不適当なのでbindに変更した。

import java.util.Scanner
object ScalaTest {

  case class IO private (x: String, performer: () => String) {
    def this(x: String) { this(x, null) }
    protected def this() { this(null) }
    def perform: String = performer();
    def bind(func: (String) => IO) = IO(null, () => (func(this.perform).perform));
  }

  case object GetLine extends IO {
    val scanner: Scanner = new Scanner(System.in)
    override def perform = scanner.nextLine
  }

  case class PutStr(str: String) extends IO(str) {
    override def perform = { print(str); null }
  }
  
  def main(args: Array[String]) {

    val main1 =
      PutStr("please input string: ").
        bind((String) => GetLine.bind(
          (line: String) => PutStr(line + "\n")
        ))

    val main2 =
      PutStr("please input string: ").
        bind((String) => GetLine).
        bind((line: String) => PutStr(line + "\n"))

    main1.perform // 処理系
    main2.perform // 処理系
  }
}

おそらくモナド則も満たしているかと思う。

要点はやはり、パイプラインを作成しておき、それを処理系に使わせる（performを呼び出させる）という点。すると、パイプラインの一番奥のもなどのperformを実行して、その結果にモナディック関数を適用した結果のモナドのperformを実行し。。。という手順になるようだ。

 BufferedReader r = new BufferedReader(new InputStreamReader(new FileInputStream("something")));

こんなパイプラインを作成しておくのに似ている。

参考

モナド