関数型プログラミング (functional programming) の利点を説く際によく持ち出されるのが、QuickCheck の開発者の一人である John Hughes が 1984 年に著した論文 "Why Functional Programming Matters" だ。「なぜ関数プログラミングは重要か」という題名で日本語訳もされているので、読んだことがある人も多いと思う。

要旨としては、冒頭の１章および２章で述べられている「関数型プログラミングが優れているのは、高階関数と遅延評価という、モジュール同士を貼り合わせる強力な『糊』を持っているからだ」という話がほぼ全てで、以降はそれを具体例に基づいて説明する構成になっている。ただ、その具体例として「数値計算アルゴリズム」やら「ゲーム用人工知能アルゴリズム」やらの話が延々と続くし、しかもコード例が Haskell の先祖にあたる Miranda という言語で書かれているのでなかなか取っ付きづらい。

今回、来年の１月に ScalaMatsuri で「なぜリアクティブは重要か」というお題で話をさせて頂けることになったこともあって、少し頑張って、元ネタであるこの論文を通読したので要約を公開したいと思う。なお、コード例は Scala で書いた（Scala 版のコードはこの記事を参考にしている）。

1. イントロダクション

本論文の目的は、関数型プログラミングの重要性を示すと共に、その利点を明確にしてフル活用できるようにすること
関数型プログラミングでは、プログラム全体を関数だけで構成する
- メインプログラム自身が関数であり、プログラムへの入力を引数として受け取り、結果をプログラムの出力として供給する
- メイン関数はさらに多くの関数を使って定義されるので、プログラムの最下層に至るまで関数は言語のプリミティブとなっている
関数型プログラミングの「利点」:
- 関数型プログラムには副作用（≒代入文）がないのでバグが減らせる
- 参照透明なので実行順序を気にしなくてよく、式をどの時点で評価してもよいのでプログラムをより数学的に扱える
それはそうなんだけど…
- 「〜ではない」についてばかり語っている（代入文がない、副作用がない、制御フローがない）
- 「〜である」について語らないと、物質的な利益に興味がある人にはピンと来ないだろう
関数型プログラミングの力を語るだけでなく、それが目指す理想を示さねばならない

2. 構造化プログラミングとの類似

関数型プログラミングと構造化プログラミングを比較してみる
構造化プログラミングとは、「goto 文を含まず」「ブロックが複数の入口や出口を持たない」
- さきほどの関数型プログラミングの「利点」と同様に、否定形の説明になっている
- 「本質的な goto」のような実りのない議論の温床になった
構造化プログラミングの核心はモジュール化であり、大きな生産性向上をもたらす
1. 小さなモジュールは素早く簡潔にコーディングできる
2. 汎用モジュールの再利用によって、プログラムをより速く開発できる
3. モジュールは独立してテストできるので、デバッグが容易になる
goto は小規模プログラミングでしか役立たないが、モジュール化設計は大規模プログラミングにおいても役立つ
プログラミング言語が問題をモジュール化する能力を高めるには、モジュール同士を貼り合わせる糊が重要
- 問題を部分問題に分割し、部分問題を解き、その解を合成する。つまり、問題を分割する方法は、解を合成する方法に依存する
- 例: 椅子を部品（座部、脚、背もたれなど）に分けて作れるのは、ジョイントや木工接着剤があるから。さもなければ、一つの木の塊から椅子を掘り出すしかない

3. 関数の貼り合せ

この章では、二種類の糊の一つ目である「高階関数」について紹介している。sum のような単純な関数を、高階関数とその引数の組み合わせとしてモジュール化することで、reduce のような汎用的な関数を導出する。

論文では、二つのデータ型（リストとツリー）に対して適用できる高階関数について述べている。まず、リスト操作関数の汎用化を進めて、最終的に reduce 関数と map 関数を導出する。次に、木（ツリー）構造に対する操作についても同様に redtree と maptree を導出する。

章の最後では、「汎用の高階関数と特有の特殊関数の組み合わせとして部品化することで、たくさんの操作を容易にプログラムできる」「新たなデータ型を定義したときは、それを処理する高階関数を書くべきだ」と結んでいる。

リスト編

リスト処理の問題を例に説明する。リストのデータ構造を（Scala で）書くとこうなる:

sealed trait ListOf[+X]
case object ListNil extends ListOf[Nothing]
case class Cons[X](head: X, rest: ListOf[X]) extends ListOf[X]

以上のデータ構造を使って具体的なリストを表すとこうなる:

[]        は ListNil
[1]       は Cons(1, ListNil)
[1, 2, 3] は Cons(1, Cons(2, Cons(3, ListNil)))

次に、リストの要素を足し上げる関数 sum を定義してみる:

def sum: ListOf[Int] => Int = _ match {
  case ListNil         => 0
  case Cons(num, list) => num + sum(list)
}

この定義を調べると、sum に固有なのは初期値 0 と演算 + だけなのが分かる*1。つまり、sum は

一般的な再帰パターン（reduce と呼ばれる）
sum 固有の部分（0 と +）

の二つにモジュール化して、後で貼り合わせることでも作ることができる:

def add(x: Int, y: Int) = x + y
def reduce[A, B](f: (A, B) => B, x: B)(list: ListOf[A]): B = list match {
  case ListNil    => x
  case Cons(a, l) => f(a, reduce(f, x)(l))
}

def sum: ListOf[Int] => Int = reduce(add, 0)

（注: Scala でこの書き方をするとスタックが溢れるけど、回避方法は色々なところで紹介されているので略。あと、カリー化の話も略。）

reduce は（初期値と演算を入れ替えるだけで）様々な用途に再利用できる:

// リストの全要素の積
def product: ListOf[Int]     => Int     = reduce(multiply, 1    )
// リストの要素のいずれかが true か調べる
def anytrue: ListOf[Boolean] => Boolean = reduce(or,       false)
// リストの全要素が true か調べる
def alltrue: ListOf[Boolean] => Boolean = reduce(and,      true )

ところで reduce は、リストの Cons の部分を f で、ListNil の部分を a で置き換えたものと看做せる:

                     l =     Cons(1,     Cons(2,     Cons(3, ListNil)))
     reduce(add)(0)(l) =      add(1,      add(2,      add(3,       0)))
reduce(multiply)(1)(l) = multiply(1, multiply(2, multiply(3,       1)))

つまり、reduce(Cons, ListNil) は（Cons を Cons に、ListNil を ListNil に置き換えているだけなので）リストからリストを複写する関数とみなせるし、リスト a と b に対して reduce(Cons, b)(a) は二つのリストを連結する関数となる:

def copy[A](l: ListOf[A])                 = reduce(Cons[A], ListNil)(l)
def append[A](a: ListOf[A], b: ListOf[A]) = reduce(Cons[A], b      )(a)

次に、リストの全ての要素を２倍したリストを返す関数 doubleAll は、doubleAndCons 関数を使って以下のように定義できる:

def doubleAndCons(num: Int, list: ListOf[Int]) = Cons(2 * num, list)

def doubleAll(l: ListOf[A]) = reduce(doubleAndCons, ListNil)(l)

doubleAndCons 関数は、以下のように double 関数と fAndCons 関数の組み合わせに置き換えられる:

def double(n: Int) = 2 * n
def fAndCons[A, B](f: A => B)(el: A, list: ListOf[B]) = Cons(f(el), list) // 2 * num => f(el)

def doubleAndCons: (Int, ListOf[Int]) => ListOf[Int] = fAndCons(double)

ところで fAndCons 関数は f と Cons を合成した関数 (Cons . f) として定義することもできる:

def fAndCons[A, B](f: A => B): (A, ListOf[B]) => ListOf[B] = (Cons[B] _).compose(f)

（注: 上記を実行するには、あらかじめ以下の暗黙変換を定義して import RichFunction2._ しておく必要がある。）

implicit class RichFunction2[T1, T2, R](f: Function2[T1, T2, R]) {
  def compose[A](g: (A) => T1): (A, T2) => R = (x: A, y: T2) => f(g(x), y)
}

したがって、doubleAll 関数は double, Cons, reduce の組み合わせで定義できる:

def doubleAll: ListOf[Int] => ListOf[Int] = reduce((Cons[Int] _).compose(double), ListNil)

ここで、double 関数をパラメータ化すると、リストの全要素に f を適用する map 関数を導出できる:

def map[A, B](f: A => B): ListOf[A] => ListOf[B] = reduce((Cons[B] _).compose(f), ListNil)

def doubleAll: ListOf[Int] => ListOf[Int] = map(double)

map は汎用的に使える有用な関数で、例えば行列（＝リストのリスト）の要素を足し上げる関数を作りたくなっても、以下のように簡潔に書ける:

def sumMatrix: ListOf[ListOf[Int]] => Int = sum.compose(map(sum))

ツリー編

ラベル付きの順序付きツリーについて考えてみる。（Scala で）データ構造を書くとこんな感じ:

sealed abstract class TreeOf[A] {
  def label: A
  def subtrees: ListOf[TreeOf[A]]
}
case class Node[A](label: A, subtrees: ListOf[TreeOf[A]]) extends TreeOf[A]

例えば、以下のようなツリーを:

    1 o
     / \
    /   \
   /     \
2 o       o 3
          |
          |
          |
          o 4

上記で定義したデータ構造で表すとこうなる:

Node(1,
     Cons(Node(2, ListNil),
          Cons(Node(3,
               Cons(Node(4,
                    ListNil),
               ListNil)),
          ListNil)))

リストの時と同様に、reduce と同じ役割を果たす redtree 関数を考えてみる。reduce は「Cons を置き換える何か」と「ListNil を置き換える何か」の二つを引数に取る関数だった。同じ方針で考えてみると、redtree は Node と Cons と ListNil を置き換えた三つの何かを引数に取る関数になるはずだ。

def redtree[A, B, X](f: (X, A) => B, g: (B, A) => A, a: A)(tree: TreeOf[X]): B = {
  def redtreeImpl[A, B, X]
      (f: (X, A) => B, g: (B, A) => A, a: A)(subtrees: ListOf[TreeOf[X]]): A =
    subtrees match {
      case Cons(subtree, rest) => g(redtree(f, g, a)(subtree), redtreeImpl(f, g, a)(rest))
      case ListNil => a
    }

  f(tree.label, redtreeImpl(f, g, a)(tree.subtrees))
}

reduce と同様に、redtree を他の関数と組み合わせて様々な関数が定義できる:

// ツリー全体の label を足し合わせる関数
def sumtree: TreeOf[Int] => Int       = redtree(add,     add,       0      )
// ツリー全体の label のリストを作る関数
def labels[A]: TreeOf[A] => ListOf[A] = redtree(Cons[A], append[A], ListNil)

最後に、ツリー用の map 関数である maptree を redtree を使って定義しておく（５章でゲーム用人工知能を実装する際に使う）:

def maptree[A, B](f: A => B): TreeOf[A] => TreeOf[B] =
  redtree((Node[B] _).compose(f), Cons[TreeOf[B]], ListNil)

インターミッション

ちょっと力尽きたので、今回はここまで。続きはやる気が湧いたら、ということにさせてください…。

論文では、高階関数がプログラムのモジュール化に役立つ理由について「データ型の詳細に関する知識を高階関数の中に局所化できる」と述べているが、これを逆に言うと「特定のビジネスロジックを実装した関数を、それを適用する（データ型の）文脈から切り離せる」ということになる。

で、この考え方を推し進めると、一例として「抽象的な Future」が述べているような、「本番用の非同期実行の文脈」と「テスト用の同期実行の文脈」を同じコードで切り替えるみたいな仕掛けが実現できるようになる、というわけですね。

*1:分かってる人向けの言い方をするなら、モノイドの単位元と二項演算。

Okapies' Archive

「なぜ関数プログラミングは重要か」を要約してみた（その１）