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

配列を破壊的に扱うデータ構造を使ったプログラム

前回は、破壊的な配列操作を関数的な配列の初期化に利用する場合について検討しました。今回は、配列を最後まで破壊的に扱うプログラムについて検討します。配列を破壊的に扱うプログラムでは、配列をそのままで利用するだけでなく、配列を他のデータ構造の一部として利用することが少なくないため、そのような例を取り上げます。
ヒープというデータ構造を考えます。ヒープは第25回でも取り上げたデータ構造で、プライオリティキューを実装するための代表的なデータ構造です。
まず、ヒープを表すデータ構造を定義します。ヒープオブジェクトは、内部に配列を持ちますが、これは破壊的に更新される配列であるため、一意配列として保持します。

class Heap:
    def __init__ (self, arr, lastindex):
        self._arr = arr
        self._lastindex = lastindex
    def new (size):
        return Heap(createUniqueArray(None, size), 1)
    new = staticmethod(new)

ヒープに対して要素を追加する処理は次のように書きます。ヒープオブジェクトを受け取って、オブジェクトが持つ一意配列を取り出し、それに対して更新処理を行って、最後に新しいヒープオブジェクトを作成して返します。

def insertHeap (heap, e):
    arr = heap._arr
    lastindex = heap._lastindex

    lastindex = lastindex + 1
    arr = update(arr, lastindex, e) # -- (1)
    idx = lastindex
    while idx > 1:
        idx2 = idx / 2
        e1, arr = select(arr, idx)
        e2, arr = select(arr, idx2)
        if e2 > e1:
            arr = update(arr, idx, e2)
            arr = update(arr, idx2, e1)
            idx = idx2
        else:
            break

    return Heap(arr, lastindex)

ここで、同じヒープオブジェクトは、insertHeap関数を一度しか呼び出せないことに注意してください。次のように、同じヒープオブジェクトに対してinsert関数を２回呼び出すと、２回目の呼び出しの際に、(1)のupdate関数のところで、UniqueErrurが発生します。

heap0 = Heap.new(16)
heap1 = insertHeap(heap0, 1)
heap2 = insertHeap(heap0, 2) # UniqueErrorが発生

一般に、内部に一意オブジェクトを持つようなオブジェクトは、やはり一意にしか取り扱うことができません。そのため、この例ではヒープオブジェクトも一意オブジェクトとして取り扱うべきです。それを考慮してプログラムを書き直すと、次のようになります。

class Heap:
    def __init__ (self, arr, lastindex):
        self._arr = arr
        self._lastindex = lastindex
    def new (size):
        return Unique( Heap(createUniqueArray(None, size), 1) ) # 修正
    new = staticmethod(new)

def insertHeap (_heap, e):
    heap = fromUnique(_heap) # 修正
    arr = heap._arr
    lastindex = heap._lastindex

    lastindex = lastindex + 1
    arr = update(arr, lastindex, e)
    idx = lastindex
    while idx > 1:
        idx2 = idx / 2
        e1, arr = select(arr, idx)
        e2, arr = select(arr, idx2)
        if e2 > e1:
            arr = update(arr, idx, e2)
            arr = update(arr, idx2, e1)
            idx = idx2
        else:
            break

    return Unique( Heap(arr, lastindex) ) # 修正

このように、内部のオブジェクトの一意性が取り囲むオブジェクトに波及する効果を「一意性の伝播」と呼びます。
最後に、一意配列とヒープオブジェクトを用いて、ダイクストラ法のプログラムを作成します。

def shortestPath (graph, s, t):
    wt = createUniqueArray(MAXNUM, graph.size)
    spt = createUniqueArray(-1, graph.size)
    pq = Heap.new(graph.size)

    pq = insertHeap(pq, graph.node(s))
    while True:
        empty, pq = emptyHeap(pq)
        if empty: break

        v, pq = getMinHeap(pq)
        if v.idx == t:
            spt = fromUnique(spt) # 一意配列から関数的な配列を取得
            ls = Unique([t])
            while spt[t] >= 0:
                t = spt[t]
                ls = insert(ls, 0, t)
            return ls

        for e in graph.adjacent(v.idx):
            wtE, wt = select(wt, e.idx)
            wtV, wt = select(wt, v.idx)
            if wtE > wtV + 1:
                wt = update(wt, e.idx, wtV + 1)
                sptE, spt = select(spt, e.idx)
                if sptE < 0:
                    pq = insertHeap(pq, e)
                else:
                    pq = updateHeap(pq, e)
                spt = update(spt, e.idx, v.idx)

    return None

shotestPath関数は、内部が３つの一意オブジェクト（２つの一意配列と１つのヒープオブジェクト）によって直列化されたプログラムになっており、それぞれの一意オブジェクトを破壊的に更新しながら計算を進めていきます。
前回と同じく、この場合も、shortestPath関数は、外面的には全く関数的な関数であることに注意してください。引数に渡されたgraphオブジェクトは一意オブジェクトではなく、shortestPath関数の処理の間で内容が更新されることはありません。