なぜメモ化も重要か - コードの恵み

1年前ぐらいに読んでよくわからなかったけど、ようやく理解できた気がしたので書いてみる。

なぜ関数プログラミングは重要か *1

John Hughes 氏の主張

プログラムをモジュール化するには関数プログラミングのスタイルで書くといいよ。

高階関数を使うと捗る
無限を使うと捗る

20年以上前に書かれたものだが今でもこの主張は通るし Groovy でも通る。

高階関数を使う

// 基本的な関数と inject を組み合わせて処理を行う
def add(x,y) { x + y }
def mul(x,y) { x * y }
assert [*1..10].inject(0, this.&add) == 55
assert [*1..10].inject(1, this.&mul) == 3628800

// 組み合わせた処理は新しい処理として定義できる
def sum    (list) { list.inject(0, this.&add) }
def product(list) { list.inject(1, this.&mul) }
assert sum    (1..10) == 55
assert product(1..10) == 3628800

// Groovy では標準で提供されているものもある
assert [*1..10].sum() == 55

データ構造ごとに高階関数を定義すると捗るらしい。
Groovy の Collection には予め高階関数が定義されているので普段から使っている。
Haskell の foldr を理解するときにここの説明がとてもわかりやすかった。
他に Groovy にはない Tree 構造に対する inject の定義も書かれている。

フィボナッチ数列で考える

無限を使う例が個人的に理解の妨げになった。平方根、微分、積分である。
許容誤差の範囲に収まるまでループしながら処理するのだが、無限を使うことより数学に話を持っていかれるのでここではフィボナッチ数列で考える。

100 から 1000 までのフィボナッチ数を表示する

再利用を考えずに書いてみる

def (a,b) = [0,1]
while (a < 1000) {
  if (100 <= a && a < 1000) println a
  (a,b) = [b,a+b]
}
// 144
// 233
// 377
// 610
// 987

さらに11番目から20番目までのフィボナッチ数を表示することになると再度フィボナッチ数のループが必要になる。
フィボナッチ数ならまだいいが複雑な処理になるが2つになるとメンテナンスが面倒だ。
そこで考えを変えてフィボナッチ数列を作る部分と数列から条件に当てはめる部分を分けておくと再利用しやすい。
フィボナッチ数列は予めどこまで必要かわかっていないので無限に生成するようにする。

Iterator を使う

遅延評価なら無限に生成するしても問題ないという話なのだが、Groovy では使えないので Iterator を使う。
Iterator は無限に続くが必要な部分だけ取り出せばよい。

def fib() {
  def (a,b) = [0,1]
  return new Iterator() {
    @Override boolean hasNext() { true }
    @Override def next() {
      def cur = a
      (a,b) = [b,a+b]
      return cur
    }
    @Override void remove() { throw new UnsupportedOperationException() }
  }
}

// 100から1000までのフィボナッチ数を表示する
// dropWhile, takeWhile は Groovy 1.8.7 以降
//println fib().dropWhile{ it < 100 }.takeWhile{ it < 1000 }.collect()

// 11番目から20番目までのフィボナッチ数を表示する
println fib().drop(10).take(10).collect()

ジェネレータを使う

Python 風のジェネレータを使うとループと同じ形式で記述できて便利だ。
http://groovy.codehaus.org/Roadmap によると Groovy3.0 (バージョンがずれたので旧Groovy2.0) で導入されるらしい。
今回はこのあいだ作ったもので

import static Itertools.gen

def fib = gen{ yield ->
  def (a,b) = [0,1]
  while (true) {
    yield(a)
    (a,b) = [b,a+b]
  }
}

// 11番目から20番目までを表示する
println fib.iterator().drop(10).take(10).collect()

無限リスト便利だねという話だったのだが無限を扱えるのは無限リストだけなのだろうか？

メモ化で無限を扱う

Groovy には便利なメモ化があるのでこれでも無限を扱える。
関数型の考え方: Groovy に隠された関数型の機能、第 3 回によるとこれも関数型の機能らしい。

// n 番目のフィボナッチ数を返すクロージャをメモ化しておけば Iterator のように扱える
// 全部メモ化するとメモリを喰い過ぎるので3つだけにする(2つだと再帰してしまった)
fib = { n -> n <= 1 ? n : fib(n-1) + fib(n-2) }.memoizeAtMost(3)

// 100から1000までのフィボナッチ数を表示する
for (int i = 0; fib(i) < 1000 ; i++) {
  if (fib(i) >= 100) println fib(i)
}

// 11番目から20番目までのフィボナッチ数を表示する
for (int i = 10; i < 20; i++) {
  println fib(i)
}

終わりに

Groovy で無限を扱う方法をいくつか書いてみた。
テキストではこの後応用として○×ゲームを作るのだがまだ読んでないのでまた書くかも。

*1:翻訳された山下伸夫氏に感謝