[Prolog] DCGで双方向性のある述語を作成

最近stackoverflowでPrologの質問に良く回答しているのですが、面白そうな問題があり、自分でもプログラムを作ってみました。

質問

内容は、[1,2,3,4,1,4,7,5,7,8,9] のようなリストが与えられた際に「続いている数字は[最初の数字,最後の数字]の形で表し、そうでないものは単体の数字で表したようなリストを生成する という問題です。
[1,2,3,4,1,4,7,5,7,8,9]は[[1,4],1,4,7,5,[7,9]] に変換されます。

作っているうちにどんどんアイデアがわいてきて、はじめは長いプログラムだったのがDCG使ってエレガントな方法で実装する方法を思いつき、最後には入出力逆転してもOKなような非常に汎用的な形で作成できました。

ECLiPSeで作成(多分他の環境でも問題なく動きます):

chunk_list([])-->[],!.
chunk_list([Chunk|Rest])-->chunk(Chunk),!,chunk_list(Rest).

% sequence
chunk([First,Last])-->sequence([ First , Last ] ),{ First < Last }.

% isolated number
chunk(Val)-->sequence([Val,Val]).

sequence([First,Last]) -->
{ ( number ( First ) , number( Last ) ) -> First < Last ; true } ,
[ First ] ,
{ succ ( First , Second ) } , sequence( [ Second , Last ] ) .

sequence([Val,Val])-->[Val].

実行結果:

[eclipse 4]: phrase(chunk_list([2,[2,6],[3,5],3,7,[1,3]]),Ret).

Ret = [2, 2, 3, 4, 5, 6, 3, 4, 5, 3, 7, 1, 2, 3]
Yes (0.00s cpu)

[eclipse 5]: phrase(chunk_list(Ret),[3,4,5,2,1,6,7,88,9,4,5,6,7,2,1,2,3]).

Ret = [[3, 5], 2, 1, [6, 7], 88, 9, [4, 7], 2, [1, 3]]
Yes (0.00s cpu)

[eclipse 6]: phrase(chunk_list([[2,4],A,[2,8],3]),[2,B,4,6,2,C,4,5,6,7,D,E]).

A = 6
B = 3
C = 3
D = 8
E = 3
Yes (0.00s cpu)

最後のマッチング例は「やってみたら、できた」という実験で、自分の予想を上回る汎用性が実現できていてびっくりしました。

入出力がどちらもリストの述語を作成するときは、工夫すると双方向性が実現できることがあると思います。

Prologの真髄に触れたような気がしました。

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

次のHTML タグと属性が使えます: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>