第40回と第41回では，Stream Fusionという融合変換の手法を紹介しました。第41回で見たように，Stream Fusionという手法は，fold/buildのような従来の融合変換の手法に比べ，柔軟で優れています。しかし，処理をStream化して扱う都合上，Stream Fusionには「前から」あるいは「後ろから」といった特定の順序に従った処理しか行えない，という弱点が残っています。

　この弱点は，リストのような逐次処理を前提としたデータ構造では特に気にする必要はありません。一方，配列のようにランダム・アクセスが可能なデータ構造では，特定の順序でしかアクセスできないことは「逐次的な処理を強制され，ランダム・アクセスを効率的に利用できない」という大きな欠点になります。

　そこで今回は，ランダム・アクセスを行う処理を効率化する「Recycling」という手法を紹介します（参考リンク）。

Recyclingが必要な理由

　配列の効率化について説明する前に，Haskellの配列についておさらいしておきましょう。第19回では，IArrayクラスが提供する不変配列と，MArrayクラスが提供する可変配列という2種類の配列を紹介しました。

　配列はランダム・アクセスが可能ですが，不変配列でランダム・アクセスの恩恵が得られるのは参照処理だけです。不変配列では配列内の要素を直接書き換えられないため，更新処理ではランダム・アクセスの恩恵は受けられません。不変配列を更新するには，新しい配列を作って既存の配列の要素をコピーしなければならず，配列内の要素がn個の場合，更新処理には線形時間O(n)のコストがかかります。1回の更新につきO(n)のコストがかかるため，m個の要素を更新するにはO(n＊m)のコストがかかることになります。

　一方，可変配列では配列内の要素を直接書き換えられるので，更新コストは定数時間のO(1)で済みます。複数個の要素を更新する場合，そのコストを，更新する要素数であるmに比例したO(m)に抑えられます。つまり，可変配列では配列の参照と更新の両方を効率的に行えます。しかし，配列内の要素を直接書き換えると，大域的な副作用を起こすため，参照透明性を破ってしまう可能性があります。そこでHaskellの可変配列では，参照透明性を守るために，IOモナドやSTモナドといった特定のモナドでしか可変配列を更新できないようにすることで副作用の局所化を図っています。

　このように，不変配列と可変配列の利点と欠点は対照的です。不変配列は便利に使えるものの非効率で，可変配列は効率的に使えるものの不便です。不変配列と可変配列の利点をなんとか組み合わせ，それぞれの欠点を克服……とまではいかなくても軽減できないでしょうか。

　この問題の解決策の一つが//演算子です。

-- Bulk updates
-- ------------

-- | /O(m+n)/ For each pair @(i,a)@ from the list, replace the vector
-- element at position @i@ by @a@.
--
-- > <5,9,2,7> // [(2,1),(0,3),(2,8)] = <3,9,8,7>
--
(//) :: Vector a   -- ^ initial vector (of length @m@)
                -> [(Int, a)] -- ^ list of index/value pairs (of length @n@) 
                -> Vector a
{-# INLINE (//) #-}
(//) = (G.//)

　//演算子では，連想リストを取って配列を更新することで，複数個の要素の更新をまとめて行います。これにより「一つの要素の更新ごとに配列を再作成する」という無駄を防いでいます。不変配列に対するO(n)の更新処理は1回だけで済むため，複数個の要素を更新する必要があっても，O(n)に更新する要素の数であるmを掛けたO(n＊m)ではなく，O(n)で処理を行うことができるのです。

　しかし，これだけでは問題は解決しません。配列を使った処理では，「v // xs // ys // ...」のように//演算子を連続して使うことがあります。この式では，//演算子の数と同じだけ配列が再作成されるため，//演算子がm個あれば，結局，配列の更新にO(n＊m)のコストがかかることになります。

　そこで，可変配列を使って不変配列の更新演算を再実装し，不変配列に対する更新コストを削減することを考えてみましょう。配列の参照透明性を守るには，更新後の配列が更新前の配列とは別に存在する必要があります。このため，可変配列を使って不変配列を実装しても，更新コストを定数時間にすることはできません。しかし，可変配列を利用することで，配列の作成回数を減らすための工夫を加えることはできます。

　先の「v // xs // ys // ...」の例で考えてみましょう。まず，「v // xs」の更新処理を行うために，wという可変配列を作成するとします。wをプログラムの他の場所で使用しないのであれば，「w // ys」を処理するために新しい可変配列を作成するのではなく，wを「再利用（Recycle）」することで，配列の再作成を減らせます。このような工夫によって連続する//演算子による配列の作成回数を1回に減らせば，更新処理のコストをO(n＋m)に下げられます。

　このように可変配列を使い回す手法がRecyclingです。HackageDBで提供されているvectorパッケージでは，配列の作成回数を減らすためにRecyclingを利用しています。