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

関数プログラミングにおける配列の問題

前回は、配列がどのような特徴を持っているかと、プログラミングにおいてどのような役割を持っているかについて説明しました。今回は、関数プログラミングにおいて配列が孕む問題について説明します。
関数プログラミングの特徴は参照透明です。参照透明が成立するには、一度値を変数に束縛したら、そのあと変数に格納された値が変わってはいけません。これは、配列の要素についても同じことが言えます。次のプログラムを見てください。

def func (ls): return ls[1]

ls = [1,2,3]
a = func(ls) // -- (1)
ls[1] = 10
b = func(ls) // -- (2)

(1)と(2)は全く同じ式ですが、aとbの値が異なるため、参照透明なプログラムではありません。一般的に配列の要素の代入は参照透明な操作ではありません。これは、スコープのルールを利用しても正当化できない操作です。
しかし、前回のアルゴリズムを見ても分かるとおり、配列の要素の代入は、配列を使ったアルゴリズムにおいて重要な役割を果たしています。そのため、配列の代入操作を禁止することは、配列を機能を著しく損ねることになります。
関数的に配列を更新する１つの方法は、配列の要素に代入を行うたびに、配列全体をコピーして新しい配列を作成するという方法です。次のような関数を用意して、配列に代入するところでは必ずこの関数を利用することで、関数的に配列を更新することができます。

def update (ls, idx, value):
    ls2 = [v for v in ls]
    ls2[idx] = value
    return ls2

これを用いると、上のプログラムは次のように書き換えることができます。このプログラムは関数的です。

def func (ls): return ls[1]

ls = [1,2,3]
a = func(ls) // -- (1)
ls = update(ls, 1, 10)
b = func(ls) // -- (2)

しかし、この方法は非常に大きな問題があります。もともと、配列の更新は定数時間の操作でした。しかし、このupdate関数は配列の要素をすべてコピーするため、O(N)の時間がかかります。このことは、配列を用いたアルゴリズムの効率を著しく低下させることになります。
また、配列は時に非常に多くの要素を格納することがあります。32bit整数の100万要素の配列は4MBのメモリを消費しますが、update関数は代入操作を行うたびに4MBの配列をコピーするためメモリ効率が著しく低下します。もともとの配列操作が非常にメモリ効率がよいこととは対照的です。