クラウド温泉3.0 (4) / 永続データ構造

クラウド温泉3.0@小樽のセッション「Monadicプログラミング・マニアックス」で使用するスライドのネタ検討その4です。

セッションはMonadicプログラミングがテーマですが、その前提として関数型プログラミングがあります。関数型プログラミングの基本構成要素も色々ありますが、オブジェクト指向プログラマの認知度が低いと思われるものに代数的データ型と永続データ構造があります。

関数型プログラミングの基本構成要素として、前々回、前回に代数的データ型を説明しました。

もう一つ重要な基本構成要素として永続データ構造があります。

「永続」というと「永続性」という概念があり永続データや永続オブジェクトといった用語は広く使われています。オブジェクト指向プログラマが「永続」と聞くと、普通は永続データや永続オブジェクトの永続を想起すると思います。

関数型プログラミングの永続データ構造は全くの別物なので注意が必要です。

永続データ構造

Wikipediaによると『永続データ構造（えいぞくデータこうぞう、英: Persistent data structure）は、変更される際に変更前のバージョンを常に保持するデータ構造である。このようなデータ構造は、更新の際に元のデータ構造を書き換えるのではなく、新たなデータ構造を生成すると考えられ、イミュータブルなデータ構造の構築に利用可能である』と定義されています。

(やや不正確ですが)簡単にいうとイミュータブルオブジェクトでデータ構造を構築したものと考えると分かりやすいと思います。イミュータブルオブジェクトは「不変」すなわち「更新不可」のオブジェクトです。更新不可のオブジェクトでデータ構造を構築すると、データの更新ができなくて困るのではないかと疑問に思ってしまいますが、関数型プログラミングではこの問題を回避するテクニックが用意されており、案外大丈夫なのです。

イミュータブルオブジェクトでデータ構造を構築すると以下のメリットがあります。

• データが変更されないのでバグが出にくい。
• 並行プログラミングでロックが必要なくなる。
• 過去のデータと現在のデータをマルチバージョン的な切り口で使用できる。

「更新不可のオブジェクトを更新する」という矛盾を関数型プログラミングのテクニックで回避することで、これらのメリットを享受することができるようになります。

特に重要なのは並行プログラミングとの相性がよい事です。並行プログラミングでのバグの多くは排他漏れによるデータのアクシデンタルな更新ですが、「データが変更されない」のでこの問題は起きません。「並行プログラミングでロックが必要なくなる」というのも大きいですし、「過去のデータと現在のデータをマルチバージョン的な切り口で使用できる」ことで多重性能を上げることにも寄与します。

「Monadicプログラミング」の狙い」の一つとして並行プログラミングを挙げましたが、永続データ構造も同様に並行プログラミングに向けてのキーテクノロジといえます。

List

「楽々Scalaプログラミング」では永続データ構造としてListの例を説明しました。

楽々Scalaプログラミング from Tomoharu ASAMI

Listは典型的な永続データ構造なので、Listの使い方に習熟することが永続データ構造をマスターする近道となります。

fold

Listが典型ですが永続データ構造を効率よく操作するためには、ちょっとしたテクニックが必要で、その一つが畳込み処理を行うfold処理をめぐるプログラミング戦略です。

このあたりの事情は「foldの選択」でも説明しました。

スライド

永続データ構造について色々と書いてきましたが、セッションではこれを一枚のスライドにまとめてざっくりと触れるという感じになると思います。

「楽々Scalaプログラミング」と同様にList処理を例に説明するかもしれませんが、時間的な制約があるのでごく簡単に触れるのみにする可能性が高そうです。

ノート

セッションは、「これからScalaプログラミングを始めたい」から「Scalaを始めたばかりで関数型プログラミングへの取り組み方法が分からない」といった、Javaプログラマを念頭に置いています。(もちろん、本当のJavaプログラマである必要はなくて、Java的なOOPを一通り使えるプログラマ、ぐらいの意味です。)

セッションではMonadicプログラミングの面白いところ、具体的な効用といったものをフィーチャしたいわけですが、細かい議論をするためには、その前提として関数型プログラミングの基礎知識が必要です。この「関数型プログラミングの基礎知識」を説明しだすと、それだけでひとつのセッションになるので、そのあたりをどうするのかが悩みどころです。

そういう意味で、セッションはMonodicプログラミングのコードを見てもらって、そのコードゴルフ的なシルエットを鑑賞?してもらいつつ、Monadicプログラミングの狙いや効用を説明していく感じになりそうです。

ただ、これだけだと不親切なので、Monadicプログラミングに必要な前提知識をリストアップしておきたいのですが、オブジェクト指向プログラマに馴染みの薄い概念として代数的データ型や永続データ構造は有力な候補かなと考えています。