最近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で作成(多分他の環境でも問題なく動きます）:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
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]. |
実行結果：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
[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の真髄に触れたような気がしました。