最近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の真髄に触れたような気がしました。