RAS Syndrome

冗長。

関数型脳になろう 〜 脱 for 文編 〜

プログラミング

「Elixir を始めたが、関数型の考え方がよく分からない」という知人に向けて書いた。

関数型プログラミングの世界では本当は、"代入"ではなく"束縛"、"返し値"ではなく"評価値"という言葉を使わないといけない。だけどその辺の説明までするのはめんどくさいので、今回は気にせずに手続き型プログラミングの世界の言葉を使った。

なぜ for 文を脱するのか

関数型っぽい考え方になるからだ。少なくとも、関数型の感覚を掴むヒントにはなるんじゃないかな。ということで詳しくは略。体感してから考えよう。Elixir 以外の関数型とか、あと Ruby とかは for 文を使わないので、とりあえず for 文以外の考え方を身につけて損はないはず。

「こんぐらい分かってるわい！」と思っても、あまり読み飛ばさないで欲しい。せっかく書いたし。何より、なんとなく感覚で理解していたものを理屈でちゃんと捉え直すというのは、とても大事なことだ。

リスト操作

リストの実装

Elixir のリストは、見た感じ片方向連結リストっぽい。

リストの再帰的定義

「リストとは何か」を定義するやり方の一つとして、以下のような形式がある。

リストとは、以下のいずれかである。

1.  [ ] （空リスト）
2.  [ なんらかのオブジェクト1個 | リスト ]

上記 2. は、コンス(cons)と呼ばれる操作をした結果であることを表す。これは、左のオブジェクトを先頭要素として右のリストにくっつける、という操作だ。片方向連結リストをイメージすれば、マシンの中で具体的に何が行われるのかもイメージできるだろう。

さて、この定義の特徴として、「リストとは何か」を述べているのに、中にまた「リスト」が出てくる、という点が挙げられる。これが「再帰的」と言われる所以だ。

果たしてこの定義は成立しているのだろうか。似たような例として、以下のような「循環定義」を考えてみる。

1. 右とは左の逆のことである。
2. 左とは右の逆のことである。

これだと何も言っていることにならない。しかし、再帰的定義は大丈夫なのである。なぜなら、1. [ ] （空リスト） の定義があるからだ。

例えば、

  • リストを自称している A は、要素 a と、リストを自称している B をコンスしたものである。
  • リストを自称している B は、要素 b と、リストを自称している C をコンスしたものである。
  • リストを自称している C は、要素 c と、リストを自称している D をコンスしたものである。

と調べていくと、自称リストの彼らは本当にリストなのか、いつまで経っても調べられないように見える。しかし実は、

  • リストを自称している D は、要素 d と、リストを自称している [ ] をコンスしたものである。
  • [ ] は定義 1. より明らかにリストである。

と、空リストさえ出てくれば議論を着地させることができるのである。以下、定義 2. を後ろから順に適用していけば、D, C, B, A は全てちゃんとリストであると言える。

どんな大きさのリストであっても、このようにして「リストの再帰的定義」を用いて本当にリストであるかどうか調べることができる。循環定義と違って、きちんと有用な定義なのである。


問題 1. [10, 20, 30, 40] がリストであることを、「リストの再帰的定義」を使って示してみよう。（なお、 [a, b, c, …] は [a | [b, c, …] ] であることを表す。また、[a] は [a | [ ] ] であることを表す。）


再帰的に定義できるデータ構造を、再帰的に処理する

さて、リストが再帰的なデータ構造に見えてきただろうか。次にいよいよ、このリストを操作する関数について考える。

例えば、数字のリストに対して合計を返す関数を考えてみよう。なお、しばらくは Enum モジュールや List モジュールを使うのは禁止だ。

defmodule Sample do
  def sum(nums) do
    # ?
  end

  def test do
    IO.puts(sum([]) === 0)
    IO.puts(sum([10]) === 10)
    IO.puts(sum([10, 20, 30, 40]) === 100)
  end
end

Sample.test()

実行結果が以下のようになれば成功ということになる。

true
true
true

さて、引数 nums は数字のリストだ。それ以外が来ることはここでは考えないことにする。（Elixir は型指定とかできるっぽいので、それをすれば確実だ。俺はまだその辺詳しくないので、とりあえず放置。）

数字のリストということは、「リストの再帰的定義」が使えることになる。つまり、nums は以下の 2 パターンしかありえないわけだ。

  1. [ ]
  2. [ num | nokori_no_list ]

コンスされた左と右の呼び方は色々あるが、Elixir ではどうやら head, tail が主流っぽい。気をつけて欲しいのは、 head が要素 1 個なのに対し、 tail は残り全ての要素でできたリストということだ。猫みたいな生き物を思い浮かべてしまうと、上手くイメージとマッチしないかもしれない。ここは恐竜みたいな、尻尾だけ異様に長い生き物を思い浮かべよう。

とにかく、nums は 2 つのパターンしかない。なので、その 2 つのパターンそれぞれに対して何を返せばいいか考えてみよう。ここで役に立つのがパターンマッチだ。

defmodule Sample do
  def sum(nums) do
    case nums do
      [] -> # ?
      [head | tail] -> # ?
    end
  end
end

ちょっと待った！実は Elixir ではもっと洗練された書き方がある。Haskell でもよく出てくる書き方だ。

defmodule Sample do
  def sum([]), do: # ?
  def sum([head | tail]), do: # ?
end

さて、パターンマッチを使うと、どちらのパターンに当てはまるかを判断してくれるだけでなく、head, tail のそれぞれに該当する値を入れてくれる。例えば、sum([10, 20, 30, 40]) を実行すると、 head には 10 、tail には [20, 30, 40] が入るというわけだ。

では、それぞれのパターンについて考える。まず sum([ ]) だが、無いものの合計は 0 だろうということで、ここでは 0 とする。他の考え方もできるかもしれないが（例えばエラーを起こすとか）、そうすると途端に実装が面倒になる。ここではとりあえず、そういうものかと思って見て頂きたい。

defmodule Sample do
  def sum([]), do: 0
  def sum([head | tail]), do: # ?
end

次はいよいよ sum([ head | tail ]) だ。具体的に sum([10, 20, 30, 40]) について考えてみよう。ここでは、 tail （＝ [20, 30, 40] ）もまた数字のリストであるという点に着目して欲しい。（「リストの再帰的定義」の定義 2. を考えればこれは当たり前のことである。 tail とはつまり、リストの定義の中に再帰的に出てくるリストのことだ。）

tail も数字のリストであるということは、 sum(tail) ができるということになる。ここで一つ、大事な方針の発表だ。これから、この sum(tail) を上手く利用することで、 sum 関数を定義する。

sum 関数の定義の中で sum 関数を使う。ここでは「リストの再帰的定義」と同様のことが起きている（あの時は、リストの定義の中でリストを使っていた）。つまりこれからやろうとしていることは、 sum 関数の再帰的定義というわけだ。

具体的に比較してみよう。

  • [10, 20, 30, 40] の定義には、 [20, 30, 40] が出てくる。（ [10, 20, 30, 40] とは [10 | [20, 30, 40] ] のことであった 。）
  • sum([10, 20, 30, 40]) を定義するのに、 sum([20, 30, 40]) を使う。（sum(tail) のことだ。）

こうしてみると、 sum(tail) を使った sum 関数の定義というのは、リストの再帰的構造に合わせたごくごく自然な定義だと思えては来ないだろうか。

まあ、とにかくやってみよう。コツとしては、未来の自分がもう sum(tail) の実装を完成させてくれているとイメージすることだ。今の自分は、 sum 関数の仕様として「引数の合計を返す」と考えている。ということは、未来の自分は、「 tail の合計を返す」ものとして sum(tail) を実装したはずだ。具体的にいえば、sum([20, 30, 40]) を実行すれば 20 + 30 + 40 ( = 90 ) が返ってくるはず、ということだ。

それにしても、今の自分と未来の自分を同時に考えるというのは奇妙な感じだ。まるで、タイムマシンで過去の自分に干渉しているという、 SF でよくあるシチュエーションみたいじゃないだろうか。今の自分が作ろうとしている関数を変えてしまうと、未来の自分が完成させる関数も変わってしまう。君はタイムパラドックスが生じないように関数を考えないといけない。だから、関数を作る前には仕様をしっかり考えて固めてしまうことが大切だ。

さて、今我々の手元には、 head の 10 と、 sum(tail) の 20 + 30 + 40 がある。これらを使って、引数の合計、つまり 10 + 20 + 30 + 40 を返そう。どうすればいいだろうか。もちろん、10 と 20 + 30 + 40 を足せば良い。

defmodule Sample do
  def sum([]), do: 0
  def sum([head | tail]), do: head + sum(tail)
end

リスト操作関数を作るコツをまとめよう。

  • リストの再帰的定義に合わせ、 2 つのパターンに対して何を返せばいいか考える。
  • f([ head | tail ]) のパターンでは、head と f(tail) をどう使うか考える。（これは裏技みたいなものでは無い。リストが head と tail リストでできている以上、f も head と f(tail) で作れると考えるのは、非常に自然なことだ。）


問題 2. 数字のリストを受け取ったら、その積を返す product 関数を作ってみよう。

問題 3. リストを受け取ったら、要素数を返す length 関数を作ってみよう。もちろん、組み込みの length 関数を使うのは禁止だ。ちなみに、length([ [1, 2, 3], 4 ]) === 2 で良い。（リストの中の子リストの要素数までは考えなくて良い。）（注釈の注釈になるが、「子リスト」と「コンスされたリスト」は別の概念だ。）

問題 4. 数字のリストを受け取ったら、各要素を 2 倍にしたリストを返す each_double 関数を作ってみよう。

defmodule Exercise do
  def test do
    IO.puts(each_double([]) === [])
    IO.puts(each_double([10]) === [20])
    IO.puts(each_double([10, 20, 30, 40]) === [20, 40, 60, 80])
  end
end

問題 5. 数字のリストを受け取ったら、奇数だけを取り出してリストにして返す odd_only 関数を作ってみよう。 if 文を使えば実装できるが、ガード節 when を使えるともっとかっこいいぞ。

defmodule Exercise do
  def test do
    IO.puts(odd_only([]) === [])
    IO.puts(odd_only([10, 20, 30, 40]) === [])
    IO.puts(odd_only([50, 51, 59, 60]) === [51, 59])
  end
end

問題 6. map 関数を自分で作ってみよう。ちなみに本家の仕様はこれだ。

defmodule Exercise do
  def test do
    double = &(&1 * 2)
    IO.puts(map([], double) === [])
    IO.puts(map([10, 20, 30, 40], double) === [20, 40, 60, 80])

    square = &(&1 * &1)
    IO.puts(map([10, 20, 30, 40], square) === [100, 400, 900, 1600])
  end
end

問題 7. reduce/3 関数を自分で作ってみよう。初期値を指定する方のやつだ。本家の仕様はこれ。

defmodule Exercise do
  def test do
    plus = &(&1 + &2)
    IO.puts(reduce([], 1000, plus) === 1000)
    IO.puts(reduce([10, 20, 30, 40], 1000, plus) === 1100)

    bigger = &(if &1 > &2 do &1 else &2 end)
    IO.puts(reduce([5, 5432, 999, 1234], 0, bigger) === 5432)
    IO.puts(reduce([5, 5432, 999, 1234], 100_00, bigger) === 100_00)
  end
end

【注記】 一般的に reduce 関数には、右から関数を適用していくパターンと左から関数を適用していくパターンがある。前者を仮に reduce_right 、後者を reduce_left と名付けよう。以下のような違いが現れる。

reduce_right(["a", "b", "c"], "1", fn(x, acc) -> acc <> x end) |> IO.inspect
# output: "1cba"

reduce_left(["a", "b", "c"], "1", fn(x, acc) -> acc <> x end) |> IO.inspect
# output: "1abc"

上の問題では、話の流れから reduce_right を答えとして期待していた。しかし、本家の Enum.reduce はどうやら reduce_left だったようだ。紛らわしい問題文になってしまって申し訳ない。ここでは reduce_right が作れれば問題ない。【注記ここまで】

問題 8. 問題 7. で作った reduce 関数を使って、問題 6. と同じ map 関数を作ってみよう。もしも難しかったら、まずは each_double 関数を reduce 関数で作ったあと、 2 倍している部分を関数に置き換えて一般化すると分かりやすいかもしれない。


数字操作

自然数の再帰的定義

自然数を 1, 2, 3, … とする流儀と、0, 1, 2, 3, … とする流儀があり、前者は数論などでよく使われ、後者は集合論、論理学などでよく使われる

自然数 - Wikipedia

プログラミングでは 0 始まりの数字をよく使う。ということで、ここでは後者の流儀を採用する。

リストと同様、自然数も実は再帰的に定義することができる。

自然数とは、以下のいずれかである。

1. 0
2. 自然数の次の数字

次の数字っていうのは、要は 1 足した数字のことだ。つまり 1 + 自然数 ということだ。リストの時は、ここが [ オブジェクト | リスト ] であった。オブジェクトをコンスする代わりに 1 を足す、というわけだ。

自然数の定義の中に「足す」だとか「 1 」だとか使って大丈夫なんだろうか。これはなんというか、言葉の綾だ。実際は「次の数字」って概念が先にあって、それを使っているだけだ。多分。実のところ、詳しいことは俺もよく分からない。ただ、この発想をプログラミングに落とし込むことならできる。まあ、詳しくはペアノの公理とかを参照して欲しい。

自然数の再帰処理

というわけで、みんな大好き階乗を実装しよう。

defmodule Sample do
  def fact(num) when num < 0, do: :error
  def fact(0), do: # ?
  def fact(num), do: # ?

  def test do
    IO.puts(fact(-1) === :error)
    IO.puts(fact(0) === 1)
    IO.puts(fact(1) === 1)
    IO.puts(fact(2) === 2)
    IO.puts(fact(3) === 6)
    IO.puts(fact(4) === 24)
    IO.puts(fact(5) === 120)
  end
end

Sample.test()

引数 num が負の場合は :error というアトムを返すことにした。本当は負の数の階乗も数学的定義があるのだろうが、今回はそこまで考えない。

というわけで、最初のパターンは引数が 0 のパターンだ。これは数学的定義を紐解けば一発で決まる。 0! = 1 だ。

defmodule Sample do
  def fact(num) when num < 0, do: :error
  def fact(0), do: 1
  def fact(num), do: # ?
end

問題は 2 番目のパターン。自然数の再帰的定義に合わせれば、 num の 2 番目のパターンは 1 + 自然数 だ。

リストの時と同じようにパターンマッチしてみよう。

defmodule Sample do
  def fact(num) when num < 0, do: :error
  def fact(0), do: 1
  def fact(1 + pre), do: # ?
end

1 つ前の自然数ということで、 pre と名付けた。さて、パターンマッチの結果は … コンパイルエラーだった。「パターンマッチングの中で + は使えましぇ〜〜ん！！！」と怒られてしまった。

defmodule Sample do
  def fact(num) when num < 0, do: :error
  def fact(0), do: 1
  def fact(num), do: # ?
end

仕方ないので、元に戻してやり直そう。 pre 変数の中身は自分で考えることにする。 num = 1 + pre ということは、すなわち pre = num - 1 だ。これがリストで言う tail にあたる部分になる。

リストの時と同じように議論を進めよう。データの再帰的構造に合わせて、関数も再帰的に定義する。fact 関数の定義には、 fact(pre) を活用すればいいことになる。

fact(5) を求める手順を考えよう。これが 5 * 4 * 3 * 2 * 1 を返すようにしたい。利用できるのは fact(pre) ＝ fact(num - 1) ＝ fact(4) だ。これは未来の自分が実装していて、 4 * 3 * 2 * 1 を返してくれる。我々はこれを使って 5 * 4 * 3 * 2 * 1 を返すことを考えればいい。もちろん、 5 （＝ num ） をかけるだけでそれは達成できる。

defmodule Sample do
  def fact(num) when num < 0, do: :error
  def fact(0), do: 1
  def fact(num), do: num * fact(num - 1)
end

これで完成だ。まあ、階乗の実装なんて見慣れているかもしれない。でも、リストと自然数を同じようなものとして見たことはあまりないんじゃないかな。その感覚を養って欲しくて、ちょっとしつこすぎるぐらいに説明させてもらった次第だ。


問題 9. 文字列 text と自然数 time を受け取ったら、text を time 回分繰り返した文字列を返す関数を作ってみよう。文字列のリストを返すのではなく、連結した 1 つの文字列を返して欲しい。名前は repeat にしよう。なお、 time に負の数が入ってくることはないものとする。

defmodule Exercise do
  def test do
    IO.puts(repeat("abc", 0) === "")
    IO.puts(repeat("abc", 1) === "abc")
    IO.puts(repeat("abc", 2) === "abcabc")
    IO.puts(repeat("abc", 3) === "abcabcabc")
  end
end


他の再帰的データ構造

例えば、木構造なんかは有名な再帰的データ構造だ。木構造の具体例としては、一般的なファイルシステムを思い浮かべて欲しい。フォルダとは、複数のファイルと複数のフォルダを含む入れ物だ。ほら、再帰的な定義だろう？だから、フォルダの中のフォルダの中のフォルダの中の方まで何か処理をしたい時は、データ構造に合わせて再帰で書くと良い。

みんな大好き rm -rf の -r は正確には —recursive 、つまり「再帰的」を意味する。つまり、フォルダの中のフォルダの中のフォルダの中の方まで削除するということだ。

Enum モジュールの使用

演習問題は全部解いてくれただろうか。これらを解いたなら、 Enum モジュールの filter も map も max も、全部再帰を使って自力で実装できるようになったということになる。そして、それらを全部 reduce を使って実装することもできるようになったはずだ。（え、できるようになってない！？じゃあ、やってみよう！ map は問題 8. でやってもらったから、後は filter と max だ。）

ここまできたら、 Enum モジュールと List モジュールの使用禁止令は解除だ。これからは存分に利用して良い。ここまでずっと再帰の練習をしてきたが、実際には繰り返し処理の 95% はこれらのモジュールを使って解決できるだろう。（ Range を使えば自然数処理もリスト処理に落とし込めるぞ。）でも、残りの 5% を解決するためにも、再帰の練習は避けちゃダメだ。

それにしても、 Enum モジュールの関数はなんでこんなにいっぱいあるんだろう。もちろんそれは便利だからだ。しかし、ただ便利なだけではなく、リスト処理を細かく分類できるのが大きい。 filter は要素を絞り込む処理だし、 map は要素毎に変換する処理だし、 max はもちろん最大値を求める処理だ。 for 文の場合、これらはどれも同じ for 文になってしまう。もちろん中身を見れば、具体的にどんな処理かは分かる。でも、 Enum モジュールの各関数は、中身を見る前に関数名からも情報が伝わってくる。リスト処理関数は、 for 文よりも表現力があるんだ。

再帰と for 文の比較

最後に、今まで書いた再帰処理と for 文を比較してみよう。今回は for 文を書くのに Python を使用する。でも、 Python といえば for 文と決まっているわけじゃない。本当は Python にはリスト内包表記っていう便利なものがあって（ Elixir にもあるらしいぞ）、大体の場面ではそっちを使う方が良いとされているので、勘違いしないで欲しい。

def sum(nums):
    total = 0
    for num in nums:
        total += num
    return total

上のコードで sum([10, 20, 30, 40]) を実行すると、以下のようなステップを踏むことになる。

  • total = 0
  • → total = 0 + 10 = 10
  • → total = 10 + 20 = 30
  • → total = 30 + 30 = 60
  • → total = 60 + 40 = 100

total の値は刻一刻と変わっていく。では、再帰ではどうだろう。

defmodule Sample do
  def sum([]), do: 0
  def sum([head | tail]), do: head + sum(tail)
end

同じく sum([10, 20, 30, 40]) で実行されるステップを考えてみよう。

  • sum([10, 20, 30, 40])
  • ＝ 10 + sum([20, 30, 40])
  • ＝ 10 + ( 20 + sum([30, 40]) )
  • ＝ 10 + ( 20 + ( 30 + sum([40]) ) )
  • ＝ 10 + ( 20 + ( 30 + ( 40 + sum([]) ) ) )
  • ＝ 10 + ( 20 + ( 30 + ( 40 + 0 ) ) )
  • ＝ 10 + ( 20 + ( 30 + 40 ) )
  • ＝ 10 + ( 20 + 70 )
  • ＝ 10 + 90
  • ＝ 100

記号を「→」から「＝」に変えたことに気づいただろうか。つまり、値はずっと変わっていないってことだ。ここでは式変形しか行われていない。まるで数学の問題を解くみたいに、問題を順番に変形していって変形していって、最後にこれ以上簡単にできない形になれば、それが解というわけ。

"数学みたい"。これは関数型プログラミングを捉える上でとても大事な視点だ。関数型プログラミングは、いわば優秀な生徒の数学の解答みたいなものだ。実際、上で表したステップは丸っきり数学の解答として通用するだろう（数学というよりは算数だが）。

for 文のステップは数学の解答と捉えることができない。無理やり数学の解答だと思って読んでみよう。

  • 10 + 20 + 30 + 40 を求める。 total = 0 とする。
  • やっぱり 10 を足して、 total = 10 とする。
  • やっぱり 20 を足して、 total = 30 とする。
  • やっぱり 30 を足して、 total = 60 とする。
  • やっぱり 40 を足して、total = 100 とする。
  • 答えは 100 。

意味が分からないだろう。普通に考えて、 10 + 20 + 30 + 40 を求める上での total は 100 でしかない。 total = 0 も total = 10 も、言ってしまえば嘘だ。この total は数学の解答に書くようなものではなくて、どちらかというと計算用紙に書いてあるような、筆算のメモみたいなものだ。

for 文を使った手続き型プログラミングでは、このように変数の中身を変えていく（破壊的代入と呼ばれる）。数学の解答ではこれはまずありえない。x = 60 だとして、そこに 40 を足したらもうそれは別の値だ。x + 40 = x なんて数学では普通出てこない。 x + 40 は x じゃなくて x + 40 だし、それに名前をつけたいなら x じゃなくて y とかにするだろう。

もちろん再帰の方のコードでも、 sum([10, 20, 30, 40]) の時と sum([20, 30, 40]) の時では head の中身は変わる。でも、これは良いんだ。sum([10, 20, 30, 40]) を実行している時と sum([20, 30, 40]) を実行している時では名前空間が違う。数学の解答で喩えるなら、問 1 と問 2 の解答欄で x に違う値を入れても誰も気にしないのと一緒だ。手続き型プログラミングの場合、同じ解答欄で x の値を変えてしまうから変な解答になってしまう。

さて、数学の解答みたいなプログラミングをすると何が嬉しいんだろう。申し訳ないが冒頭でも宣言した通り、ここの説明には踏み込まないことにする。「関数型プログラミング メリット」とかでググればたくさん出てくるだろうし、きっともういくつか目を通しているだろう。その調子で頑張って調べて欲しい。キーワードは、"イミュータブル"、"参照透過性"、"副作用の分離"、"宣言的"とかだろう。きっと。

一つだけ注意しておくと、関数型プログラミングは良いことばかりじゃない。なんせ、プログラミングっていうのは本来はコンピューターへの命令を記すものなんだ。まさに手続きを記すものであって、決して数学の解答なんかじゃない。そこを無理やり数学の解答みたいに書こうとすると、色々と大変な場面も出てくる。

まあ、そんな感じだ。これで関数型脳に少しでも近づけたなら、俺がこの文章に費やした労力も報われるってものだ。なのでまあ、頑張って欲しい。

追記

解答例作りました。