関数プログラミングのアプローチ (27)

関数的なデータ構造で代替する

前回見たように、関数プログラミングにおいて配列を利用することには、本質的な難しさがあります。この問題に対する対処方法には２通りのアプローチがあります。

配列を使わず、関数的なデータ構造で代替する
制限を設けて、破壊的に配列を操作する枠組みを用意する

今回は、まず最初のアプローチを概観します。

配列の代替として最も一般的なデータ構造がリスト（単方向連結リスト）です。このデータ構造は、配列と同程度にシンプルな構造をしているため、多くの関数プログラミングをサポートするプログラミング言語で基本的なデータ構造として採用されています。

リストの特徴は次のとおりです。

サイズは可変長で、実行時に動的に変化する
キーが０から始まる連続的な整数
メモリ上の表現は比較的コンパクト（ボックス化リストはボックス化配列の２倍くらいのメモリ消費）だが、分散化の傾向がある
先頭要素へのアクセスと先頭からの順次アクセスが効率的
先頭付近の要素の関数的な更新は効率的

つまり、リストは先頭付近の要素に対する関数的な更新を効率的に行うことと引き換えに、配列における次のメリットを犠牲にしたデータ構造と言えます。

きわめて効率的なメモリ上の表現
任意要素へのインデックスアクセス
任意方向への順次アクセス

ただし、リストを２つ組み合わせたZipperというシンプルなデータ構造を用いることで、更新が可能な双方向イテレータを作成することができます。そのため、要素へのアクセスがリストの先頭や順次アクセスに限られる場合には、リストは効率的な代替となります。

Finger Trees

リストは、スタックのようなデータ構造を表現するには効率的なデータ構造ですが、キューやdequeのようなデータ構造を表現するにはあまり適切ではありません。そのため、そのようなデータ構造を表現するには、そのための特別なデータ構造が必要となります。

そのようなデータ構造の中で、シーケンスを表現するための汎用的なデータ構造として、Finger Treesを取り上げます。Finger Treesは、シーケンスに対するさまざまな操作を比較的効率よく処理することができるデータ構造です。主な操作の効率は次のとおりです。

先頭と末尾へのアクセス/追加/更新/削除 - amortized O(1)
２つのシーケンスの結合/シーケンスの分割 - O(log(n))
任意要素へのアクセス/追加/更新/削除 - O(log(n))

また、Finger Treesは、インデックスが連続整数である必要はないという特徴があります。そのため、以下にあげるさまざまなデータ構造として利用が可能です。

キュー, Deque
ランダムアクセスシーケンス
プライオリティキュー

２分木

シンボルテーブルとしてのハッシュテーブルの効率は、配列の非常に効率的な特徴に依存しています。そのため、配列の代わりにFinger Treesを利用してハッシュテーブルを構築することはあまり効率的ではありません。そのため、関数的なシンボルテーブルを作成するためには、代替となるデータ構造が必要となります。

シンボルテーブルを作成するための、ハッシュテーブルに並ぶ代表的なデータ構造には、他に２分木があります。ルートからリーフに向かう単方向連結の２分木は、リストに似た構造となるため、関数的な操作が可能です。そのため、赤黒木やAVL木がハッシュテーブルの代替として利用可能です。

このように、関数プログラミングにおいては、配列が利用できない制限を回避するために、ケースに応じてさまざまな関数的なデータ構造を選択する必要があります。適切なデータ構造が見つかる場合は問題にはなりませんが、場合によっては適切なデータ構造を見つけるのが難しい場合や、配列に比べて効率が低下するという場合があります。そのため、このアプローチが常に成功するとは限らないところに注意が必要です。