Chapter 15

実例:手続き型プログラムを関数型に書き直す

とっくり
とっくり
2022.09.03に更新

はじめる前にご注意

この記事は、手続き型で書いたコードと関数型で書いたコードの違いを説明することを目的としています。どんなプログラムでも関数型にするべきだという主張ではありません。

関数型プログラミングの反対は

「関数型プログラミング」の反対は、「オブジェクト指向プログラミング」ではなくて、「手続き型プログラミング」です。

オブジェクト指向と関数型の関係はややこしいので、とりあえず相反するものではないってくらいにしときまして。

今回は、どんなプログラムが「手続き型」で、どんなのが「関数型」か、そしてその間のグラデーションについて、一つの題材を徐々に変化させていくことで説明してみたいと思います。

文と式

ちょっとだけ用語の説明です。

代入文、if文、for文、return文、返り値voidの関数など、値を持たない(左辺にconst x =などとして代入できない)コード片は文 (statement)
例:

const a = 0
console.log('hello')
if (a === 0) {
  getSomething()
}

返り値がある関数呼び出し、演算など、値を持つ(左辺にconst x =などとして代入できる)コード片は式 (expression)
例:

10 + 5
new Array(1, 2, 3)
a === 0 ? getSomething() : null

用語の説明、以上!

題材:配列のソート

最近の若い人は配列をソートするプログラムをわざわざ書くこともないと思いますが、昭和生まれ世代は一度は書いたことがあるという人が多いのではないでしょうか。

今回の記事では、配列のソートを題材にして様々な書き方を比べてみましょう。前回に引き続き、言語はTypeScriptです。

これからお見せするソート関数は全て、下記のインターフェイスSortAlgorithmを実装します。引数はイミュータブルなReadonlyArray、返り値がソート済みのReadonlyArrayです。手続き型のコードも関数型のコードもすべて副作用を持たない純粋関数です。

capture: Captureは最後のおまけのためのログ取り関数なので、読む時は無視してください。

バブルソート

bubble sort
バブルソートは配列内を二重ループで2箇所ずつ総当たりで比較して、大きい数が左側にあればひっくり返す動作(swap関数)を繰り返すと大きい数が徐々に右側に集まっていくというやり方です。

一番遅いソートアルゴリズムとして有名ですが、実装が簡単なのでも有名です。ン十年ぶりに書きましたが一発で書けました。

このbubbleSort()のコードは、内部で副作用を持つswap()関数を使っていますが、全体としては引数以外の入力を持たず返り値以外の出力を持たないのでちゃんと純粋関数です。
※ 引数captureは無視してください。

そして「手続き型のコード」の特徴を色々持っています。

  • ミュータブルなデータ構造Array<number>を主に使っている
  • 文(代入文、for文、if文、return文、swap関数)を並べてロジックを表現している

バブルソートは、アルゴリズムのアイディア自体が手続き型プログラミングを前提としているので、ある意味これがアイディアをそのまま表現した正解の実装と言えます。

普通のクイックソート

クイックソートは非常にシンプルなアイディアで省メモリで実行速度も最速レベルという大変ありがたいアルゴリズムです。

quick sort

クイックソートの手順は以下です。

  1. 関数「クイックソート」
  2. 配列中の任意の要素をpivotとする。(本記事ではソート範囲の最初の要素を選ぶ)
  3. pivotより小さい要素をpivotより左側に集める。
  4. pivotより大きい要素をpivotより右側に集める。
  5. 左側部分が2要素以上なら、さらに関数「クイックソート」でソートする。
  6. 右側部分が2要素以上なら、さらに関数「クイックソート」でソートする。

引数に与えられるinitial配列はReadonlyArrayでイミュータブルなので、別のミュータブルな配列に1回だけコピーし、あとはその配列内の入れ替えだけで実現したのがこちらのコードです。

上の手順3と5のpivotより小さい要素と大きい要素をそれぞれ集めるのを配列内の入れ替えだけで実現するのが難しくて、何度も失敗してはやり直しました… 😑

このコードは、一般的なアルゴリズムの教科書と大体同じになっているはずです。

富豪のクイックソート(見たまんまのコード)

ここからクイックソートのコードを書き換えていきます。

上の「正解」のコードは、クイックソートを確実に実現できているのですが、最初に書いたクイックソートの手順のようなシンプルなアイディアをパッと見で読み取るのはかなり難しいと思います。

なんかwhileの二重ループがあって、内側のwhile文でleftrightを変化させて、なんかの条件で配列の要素入れ替えをして…うん、わからん。

そこで、手順中の

  1. pivotより小さい要素をpivotより左側に集める。
  2. pivotより大きい要素をpivotより右側に集める。

という部分をそのまんまコードで表現してみたのがmillionaireQuickSortです。

省メモリ性能を犠牲にしてsmallerlargerという2つの配列を作り、pivotより小さい値と大きい値をそれぞれpushしています。とても読みやすく書きやすいですね。

そしてできたsmallerlargerを再帰的にmillionaireQuickSortに渡してソートして、sortedSmallerpivotsortedLargerの順にArray.concat()で連結すればできあがりです。

前のコードと比べると、ローカル変数への代入文、swap関数、if文、while文のネストが減りましたが、ミュータブルな配列smallerlargerにforループでpushしていくところが手続き型の特徴を残しています。

大富豪のクイックソート(イミュータブル)

富豪のクイックソートはだいぶ読みやすくなりました。ただ、「pivotより小さい要素の集合と大きい要素の集合に分ける」というアイディアを知らない場合は、forブロックの中を注意深く読んで初めて「あぁ値の大小で分けてるのか」と分かるだろうというレベルです。

このアイディアをもっとそのまんま表現できる書き方をしたのが下記のbillioaireQuickSortです。

「arrのうちpivotより小さい要素の集合」はArray.filter()を使って

arr.filter((num) => num < pivot)

のように、アイディアをそのまんま表現できます。

「いや、なにがそのまんまやねん」という向きもあるかもしれません。Array.filter()メソッドの仕様とラムダ式に慣れる必要があるのですが、そこに慣れるともうこれは「arrのうちpivotより小さい要素の集合」としか読めなくなるのです。

それをさらにbillionaireQuickSortでクイックソートしたのがsortedSmallerというわけです。(※captureはログ取り用なので無視してください)

富豪のクイックソートではforループ一回りでsmallerlargerの両方を作りましたが、大富豪のクイックソートでは配列の全要素をループするfilterを2回使ってるのでさらに少し実行時間が増えます。

あと地味にarr.slice(1)で0番目を取り除いた新しい配列を作ってるところもメモリと時間を使ってますね。

これでまた手続き型の特徴が減り、だいぶ関数型っぽくなりました。

  • ミュータブルなデータ構造が無くなった
  • ローカル変数はpivotsortedSmallersortedLargerの3つだけになり、どれも関数の根本的なアイディアの一部分を表現する役割を果たしている
  • 文は代入文とreturn文と冒頭のif文だけになった
  • const smaller = ...の部分は関数(ラムダ式含む)の組み合わせだけで一つのアイディアを表現している

僕の感覚としては、もうこれは関数型プログラミングだと言って差し支えないと思います。しかし、人によって意見が分かれるかもしれません。

原理主義者のクイックソート

大富豪のクイックソートはもう関数型プログラミングだと思うのですが、「いやいや、まだ文が残っているではないか」と仰る向きのためにさらに書き換えていきます。

もうミュータブルなローカル変数は無くて、出てくる関数は全て純粋関数なので、

const pivot = arr[0]
const sortedSmaller = billionaireQuickSort(......)
const sortedLarger = billionaireQuickSort(......)

の左辺の変数が出現するところを機械的に右辺の式に置き換えることができます。これが「参照透過性」です。

変数sortedSmallersortedLargerは1回ずつしか参照されてないので、右辺で置き換えても関数呼び出し回数は変わりませんね。

唯一、pivotが3回参照されてますが全部arr[0]に置き換えるのは計算量としては大した差ではないでしょう。

そして冒頭のif文を三項演算子の式に置き換えればreturn文1つだけになるので、ラムダ式の{ }ブロックとreturnを省略してprinciplistQuickSort完成です。

「うっ、一つ前のコードのほうが読みやすかった」と思うかもしれません。わかります。

しかし、この関数は少し我慢して読むと以下の特徴があります。

  • イミュータブルどころかローカル変数が一つも無い
  • 全部が式。pincipleistQuicksort本体まで含めて式しかない。
  • クイックソートのアイディアを最も短く端的に表現している
    • クイックソートは配列の長さが1以下ならそのまま返す。そうでないなら以下を連結して返す。
      • 0番目の要素より小さい値を集めてクイックソートした配列
      • 0番目の要素
      • 0番目の要素より大きい値を集めてクイックソートした配列

これが関数型ではないと言う人は、たぶんいないはずです。

まとめ

ここまで、クイックソートを題材に手続き型から関数型に徐々に変化させてきました。手続き型のコードと関数型のコードの特徴をまとめます。

手続き型コードの特徴

  • ミュータブルなデータ構造を主に使う
  • ローカル変数をたくさん使う
  • 文を順番に並べてロジックを表現している
  • ロジックのアイディアをデータ構造の一連の操作に再構築して実装する

関数型コードの特徴

  • イミュータブルなデータ構造を主に使う
  • ローカル変数の使用を最低限にする
  • 式を合成(式の値を他の式の一部とする)してロジックを表現している
  • ロジックのアイディアをそのまんま式で表現したらそれが実装になってるので、(関数型に慣れていれば)読みやすく、メンテしやすい

そしてこれら2つの間は断絶ではなく、グラデーションになっていることも示せたのではないでしょうか?

どっちがいいの?

もちろん関数型プログラミングをおすすめしている連載なので、関数型ですと言いたいですが、たとえば配列を扱う関数で要素数が数千や数万になる可能性があるとか、その関数が1秒間に何百回も呼ばれる可能性があるなら省メモリで高速に最適化した「手続き型コード」が最適です。

ではそういう性能要件がそれほどないケースではどうでしょう?実際にアプリケーションを開発する際に数千や数万要素の配列を扱うケースはそれほど多くありませんよね。せいぜいDBやAPIから取得した数十〜数百要素程度を扱うことがほとんどでしょう。

そういう状況であれば、ロジックのアイディアをそのまんま式で表現したらそれが実装になってる関数型プログラミングの「メンテナンスしやすい」という利点が大きく出てきます。つまり、ちょっと10倍ぐらい遅いコードだとしても、ユーザーを待たせる時間に0.001秒と0.01秒の差ぐらいしかないならメンテしやすいほうが良くない?と思うのです。

そんなわけで、ソートがちゃんと動いてることを確認するために一番手間を掛けて作ったおまけを表示して今回はここまで!(ちゃんと上で書いたコードを使って動いてます)