ELPI の組込述語 (std.set編)

@suharahiromichi

2022/12/13
ELPI (文献[2]) の組込述語の2回めとして、ELPIのソースコード [1]

src/builtin_set.elpi

に定義されている、集合を扱うライブラリの説明をします。全順序集合を平衡二分木を使って実装しています。

この記事の元になるソースコードは以下にあります。

std.set の使い方

述語名の前にstd.set.をつけて使います。

pred make i:(E -> E -> cmp -> prop), o:std.set E.

全順序の関係を定義して、空集合を返しまします。ここでは、基本として、整数どうしの大小関係を指定しています。

E -> E -> comp -> prop 型の3引数の述語で定義しますが、第3引数は、出力であることに注意してください。第1と第2引数の関係を調べて、eq、lt、gtのどれか（cmp型）を（決定的に）返すようにします。cmp型は、

kind cmp type.
type eq cmp.
type lt cmp.
type gt cmp.

で定義されています。いわゆる列挙型と思って間違いありません。

pred cmp1 i:int, i:int, o:cmp. /* o に注意！ */
cmp1 X X eq.
cmp1 X Y lt :- X < Y.
cmp1 X Y gt :- X > Y.

pred test1.
test1 :-
      std.set.make cmp1 _.

pred mem i:E, i:std.set E.

集合に要素が含まれているかテストします。「∈」ですね。
まだ空集合なので、not (1 ∈ ∅) です。
第1引数は値が決まっていないとだめなので、std.set.mem S Xで、Sの任意の要素Xを取り出すことはできません。

pred test2.
test2 :-
      std.set.make cmp1 S,
      not (std.set.mem 1 S).

pred add i:E, i:std.set E, o:std.set E.

要素を追加します。同じ(eqである)要素を何回追加しても、変りません。

pred test3.
test3 :-
      std.set.make cmp1 S,
      std.set.add 1 S S1,
      std.set.add 2 S1 S2,
      std.set.mem 2 S2,
      std.set.add 2 S2 S2,
      std.set.add 2 S2 S2,
      std.set.add 2 S2 S2.

pred remove i:E, i:std.set E, o:std.set E.

要素を削除します。含まれない要素の削除はfailします。

pred test4.
test4 :-
      std.set.make cmp1 S,
      std.set.add 1 S S1,
      std.set.mem 1 S1,
      std.set.remove 1 S1 S2,
      not (std.set.mem 1 S2),
      not (std.set.remove 1 S2 _).

pred cardinal i:std.set E, o:int.

集合の大きさを返します。

pred test5.
test5 :-
      std.set.make cmp1 S,
      std.set.add 1 S S1,
      std.set.add 2 S1 S2,
      std.set.cardinal S2 N,
      print "size is " N.

pred elements i:std.set E, o:list E.

集合の要素をリストで返します。

pred test6.
test6 :-
      std.set.make cmp1 S,
      std.set.add 1 S S1,
      std.set.add 2 S1 S2,
      std.set.elements S2 L,
      print "elements are " L.

集合の任意の要素を（非決定的にバックトラックによって）取り出したい場合は、std.set.elements とリストのstd.mem を組み合わせて使います。引数の順番に注意してください。

pred test6_1.
test6_1 :-
      std.set.make cmp1 S,
      std.set.add 1 S S1,
      std.set.add 2 S1 S2,
      std.set.elements S2 L,
      std.mem L X,
      print X,
      fail.

補足説明

もしご興味があれば、実装も見てみてください。Prologだからといって特別なアルゴリズムを使っているわけではありません。効率的なプログラムのためには効率的なアルゴリズムを選ばないといけないという点で、Prologは決して特別な言語ではありません。
また、集合演算としては、要素の追加と削除しかないので、物足りないかもしれません。そう思ったかたは、ぜひ、このライブラリの拡張にも挑戦してみてください。

参考文献

[1] ELPIソースコード
https://github.com/LPCIC/elpi/tree/master/

[2] λProlog (Lambda Prolog) の紹介
https://qiita.com/suharahiromichi/items/a046859da0c0883e7304

[3] ELPI の組込述語 (stdlib編)
https://qiita.com/suharahiromichi/items/1d200a9320e04ca21953