3.2 差分リスト

先程の例では, ソートされた木を生成することはできたが, ソートされた結果を 外に出していない. 結果を外に出す時には,先程のFIFO法があるが, それだけでは 結果を出力する窓口が一つしかない. すでにプログラムは, 並列性を持ったプログ ラムであり, 並列に結果を並べられるような工夫が必要となる.

 
図 3.5: 並列に解が出力

ここで, 出力のための引数とは別に, 他のゴールの出力をつなぐための新たな変数を 1 つ設ける. これにより, 複数の結果出力を並行させ, それらをつなぐようにで きる. このように出力のための変数を2つ(直接出力のための変数と,以降のゴール の出力をつなぐための変数)を持ち回って, 並列処理を損なうことなく結果を収集 する技法を 差分リストという.

 
図 3.6: 解の連結

差分リストは, ノード間の解を集めるのに有効な技法である. クイックソートの解 を出力するため, 差分リストの2引数(解を出力するための引数と解同士をつなぐ新た な変数の引数)を加える. プログラムは次のようになる.

  qsort(In,Out) :- true | terminal(In,Out,[]).

  node([]   ,V,L,R,Xs,Ys) :-  true   | L = [], R = [], Xs = [V|Ys].
  node([H|T],V,L,R,Xs,Ys) :-  H > V  | R = [H|NR], node(T,V,L,NR,Xs,Ys).
  node([H|T],V,L,R,Xs,Ys) :-  H < V  | L = [H|NL], node(T,V,NL,R,Xs,Ys).
  node([H|T],V,L,R,Xs,Ys) :- H =:= V | node(T,V,L,R,Xs,Ys).

  terminal([]   ,Xs ,Ys) :- true | Xs = Ys.
  terminal([H|T],Xs0,Ys) :- true |
       terminal(L,Xs0,Xs1), node(T,H,L,R,Xs1,Xs2), terminal(R,Xs2,Ys).

``qsort'' から ``terminal''に渡された差分リストは最終的に ``node''に渡り, 入力ストリームが閉じられた時に解を出力するようにしている. ここで ``node'' は, 差分リストを持ち回っているが,その差分リストを処理し ているのは, 入力ストリームが閉じられた時にのみ差分リストの単一化が 実行されている. 単一化を処理するのはいつでもよいから, ``node'' を呼び出している ``terminal'' の中で処理することができ, ``node'' への引数として渡す必要がないことがわかかる.

このようにクイックソートの原理を素直に書き下し, 整形していくと, 次のような(例題プロ グラムとしてよく出される)クイックソートのプログラムになる. (例題では node split or partition , terminal qsort になっていることが多い.)

  qsort(In,Out) :- true | terminal(In,Out,[]).

  node([]   ,V,L,R) :-  true   | L = [], R = [].
  node([H|T],V,L,R) :- H > V   | R = [H|NR], node(T,V,L,NR).
  node([H|T],V,L,R) :- H < V   | L = [H|NL], node(T,V,NL,R).
  node([H|T],V,L,R) :- H =:= V | node(T,V,L,R).

  terminal([]   ,Xs ,Ys) :- true | Xs = Ys.
  terminal([H|T],Xs0,Ys) :- true |
       terminal(L,Xs0,Xs1), node(T,H,L,R), Xs1 = [H|Xs2], terminal(R,Xs2,Ys).