Prologプログラミング: リスト処理


リスト

Prolog では,リスト (list) と呼ばれるデータ構造を使って, 任意の長さのデータ列を表すことができます. 以下のものは,リストの例です. 最初の例は,3つの要素 jan, 31, 1957 からなるリストです. 2番目の例も 3つの要素からなるリストです. 3番目の要素が,またリストになっています. 最後の例は,要素のないリスト(空リスト)です.

リストの一般形は [要素1, 要素2, ..., 要素n] です. 要素としては,任意の項が使えます. もちろん要素がまたリストであってもかまいません. 要素の数 n は,リストの長さと呼ばれます. 長さ 0 のリストは空リストと呼ばれます.

実はリストも前に説明した項の一種です. write_canonical を使って, どのように内部で表現されているのかを調べてみましょう.


    | ?- write_canonical([a]).
    '.'(a,[])
    | ?- write_canonical([b,a]).
    '.'(b,'.'(a,[]))
    | ?- write_canonical([c,b,a]).
    '.'(c,'.'(b,'.'(a,[])))
つまりピリオド ('.') を関数記号とする複合項で表現されているわけです. 木表現にするとそれぞれ下のようになります.
        [a]の木表現   [b,a]の木表現    [c,b,a]の木表現

             .             .                 .
            / \           / \               / \
           a   []        b   .             c   .
                            / \               / \
                           a   []            b   .
                                                / \
                                               a   []
この図を良く見ていると, [a] は [b,a] の一部として現れており, [b,a] は [c,b,a] の一部として現れていることに気がつきます. つまり,以下のようになっているわけです
        リスト    すべて '.' で表現         1番外側だけを '.' で表現
        [a]     =             '.'(a,[])
        [b,a]   =       '.'(b,'.'(a,[]))  = '.'(b,[a])
        [c,b,a] = '.'(c,'.'(b,'.'(a,[]))) = '.'(c,[b,a])
一般には以下のようになります (カンマやピリオドだらけでわかりにくいですが…). したがって,リスト [要素1, 要素2, ..., 要素n] を '.'(X,Y) とマッチさせたとき, X は 要素1 とマッチされ, Y は 要素1 を除いた残りのリスト [要素2, ..., 要素n] とマッチされるわけです.

    | ?- '.'(X,Y) = [a,b,c].
    X = a,
    Y = [b,c] ? 
    | ?- '.'(X,Y) = [a].
    X = a,
    Y = [] ? 
Prolog では, '.'(X,Y) という項は [X|Y] という記法でも 表すことができますから,上の例は次のようにも書けます.

    | ?- [X|Y] = [a,b,c].
    X = a,
    Y = [b,c] ? 
    | ?- [X|Y] = [a].
    X = a,
    Y = [] ? 
つまり,リストと [X|Y] をマッチさせると, 先頭の要素が X に,残りのリストが Y にマッチすることになります.

また, [X|[Y|Z]] は [X,Y|Z] と表すことができます. したがって,リストと [X,Y|Z] をマッチさせると, 先頭の要素が X に,2番目の要素が Y に, 残りのリストが Z にマッチすることになります. [X,Y|Z] と [X,Y,Z] が異なることに注意してください. [X,Y|Z] は長さが 2 以上の任意のリストにマッチしますが, [X,Y,Z] は長さが 3 のリストにだけマッチします.


    | ?- [X,Y|Z] = [a,b].
    X = a,
    Y = b,
    Z = [] ? 
    | ?- [X,Y,Z] = [a,b].
    no

リストを読む

リスト L の 1 番目の要素 X を取り出す述語 first(L,X), 2 番目の要素 X を取り出す述語 second(L,X) を定義してみましょう.

    first([X|_], X).
    second([_,X|_], X).
N 番目の要素を取り出すには,再帰的にプログラムを書く必要があります.

    nth(1, [X|_], X).
    nth(N, [_|L], X) :-
        N > 1, N1 is N-1, nth(N1, L, X).
1 つ目の事実は,リスト [X|_] の 1 番目の要素は X であることを表します. 2 つ目の規則は,リスト [_|L] の N 番目の要素は, N > 1 であり L の N-1 番目の要素が X であるならば, X であることを表します.

では次に,与えられたリストの長さを求めるプログラムを書いてみましょう.


    len([], 0).
    len([_|L], N) :-
        len(L, N1), N is N1+1.
1 つ目の事実は,空リストの長さは 0 であることを表し, 2 つ目の規則は,リスト [_|L] の長さは L の長さに 1 を加えたもので あることを表します. SICStus Prolog では,組込述語 length により直接求めることができます.

では次に,与えられたリスト中の最大値を求めるプログラムを書いてみましょう.


    max_list([X], X).
    max_list([X|L], M) :-
        max_list(L, M1), M is max(X,M1).

    | ?- max_list([3,1,4,1,5,9,2,6], M).
    M = 9 ? 

リストを作る

リスト [N, N-1, ..., 2, 1] を作るプログラムを書いてみましょう. このプログラムは次のように再帰的に考えればOKです.
  1. N が 0 のときは空リストである.
  2. N が正のときは [N-1, ..., 2, 1] を再帰的に作って その前に N を付け加えればよい.
Prolog で書くと以下のようになります.

    rev_range(0, []).
    rev_range(N, L) :-
        N > 0, N1 is N-1,
        rev_range(N1, L1),
        L = [N|L1].
ところが Prolog では,等式は両辺の項が等しいという関係を表しています. したがって,上の例では L = [N|L1] とあるので, L を単純に [N|L1] で 置き換えてかまいません.

    rev_range(0, []).
    rev_range(N, [N|L1]) :-
        N > 0, N1 is N-1,
        rev_range(N1, L1).
この場合, rev_range(1, L) を実行すると, 2 つ目の規則にマッチし, L はとりあえず [1|L1] となります (値が未定義の変数 L1 を含んだままです). その後, rev_range(N1, L1) の実行により L1 が [] となり, 結果的に L は [1|[]],つまり [1] となるわけです.

では,リスト [1, 2, ..., N] を作るプログラムを書いてみましょう. この場合, [2, ..., N] というリストを再帰的に作りだす必要があります. 一般的には [I, I+1, ..., N] というリストを作りだせばよいわけです.

  1. I > N のときは空リストである.
  2. I =< N のときは [I+1, ..., N] を再帰的に作って その前に I を付け加えればよい.
Prolog で書くと以下のようになります.

    range(I, N, []) :- I > N.
    range(I, N, [I|L1]) :-
        I =< N, I1 is I+1,
        range(I1, N, L1).
range(1, 10, L) として呼び出せば L として [1, 2, ..., 10] が 得られます.

次は, Collatz の問題を改良して, 途中結果をリストとして返すようにしてみましょう.


    collatz(1, [1]).
    collatz(N, [N|L1]) :-
        N > 1, N mod 2 =:= 0, N1 is N//2, collatz(N1, L1).
    collatz(N, [N|L1]) :-
        N > 1, N mod 2 =:= 1, N1 is 3*N+1, collatz(N1, L1).
実行してみると以下のようになります. 23 から始めると 16 ステップで 1 になり, 途中の最大値は 160 であることがわかります.

    | ?- collatz(23,L), len(L,N), max_list(L,M).
    L = [23,70,35,106,53,160,80,40,20,10,5,16,8,4,2,1],
    M = 160,
    N = 16 ? 
次にリストの各要素に 1 を加えるプログラムを書いてみましょう.

    inc_list([], []).
    inc_list([X|L], [X1|L1]) :-
        X1 is X+1,
        inc_list(L, L1).
実行して見ると以下のようになります.

    | ?- inc_list([3,1,4], L).
    L = [4,2,5] ? 
一般に,リストの各要素を何かの rule によって書換えるプログラムは 次のようになります.

    replace([], []).
    replace([X|L], [X1|L1]) :-
        rule(X, X1),
        replace(L, L1).
rule として次のものを付け加えてみます.

    rule(i, '私').
    rule(you, 'あなた').
    rule(have, '持つ').
    rule(love, '愛する').
    rule(a, '一つの').
    rule(pen, 'ペン').
    rule(book, '本').
実行して見ると以下のようになります.

    | ?- replace([i,have,a,book], L).
    L = ['私','持つ','一つの','本'] ? 
    | ?- replace([i,love,you], L).
    L = ['私','愛する','あなた'] ? 

プログラム append

与えられた 2 つのリスト X, Y を連結したリスト Z を求めるプログラムを 作ってみましょう.

この問題を再帰的に考えると以下のようになります.

  1. X が空リストのとき, Z は Y に等しい
  2. X が空リストでないとき,すなわち [W|X1] の形のとき, Z は, X1 と Y を連結したリストの先頭に W を付け加えたリストに等しい
たとえば [a,b,c] と [d,e,f] を連結したリストを求めるには, まず [b,c] と [d,e,f] を連結したリストを求めて, その先頭に a を付け加えればよいわけです.

これを Prolog でプログラミングしてみると次のようになります.


    append(X, Y, Z) :-
        X = [],             /* X が空リストのとき */
        Z = Y.              /* Z は Y に等しい */
    append(X, Y, Z) :-
        X = [W|X1],         /* X が [W|X1] のとき */
        append(X1, Y, Z1),  /* X1, Y の連結 Z1 を求めて */
        Z = [W|Z1].         /* Z1 の先頭に W を付け加えたものが Z */
上の rev_range の時と同様に,等式の部分を置き換えると append のプログラムは次のように 非常に簡単な形になります.

    append([], Z, Z).
    append([W|X1], Y, [W|Z1]) :-
        append(X1, Y, Z1).
このプログラムは, 2 つのリストを連結することはもちろん, 第 3 引数に与えられたリストを 2 つのリストに分解することもできます. [a,b,c] と [d,e,f] の連結を求める例と, [a,b,c] を 2 つのリストに分解する例を示します.

    | ?- append([a,b,c], [d,e,f], Z).
    Z = [a,b,c,d,e,f] ?
    | ?- append(X, Y, [a,b,c]).
    X = [],
    Y = [a,b,c] ? ;
    X = [a],
    Y = [b,c] ? ;
    X = [a,b],
    Y = [c] ? ;
    X = [a,b,c],
    Y = [] ? ;
    no
append を使うと,与えられたリスト L の最後の要素 X を求める プログラム last(L, X) は次のように書けます. つまり,リスト L が何かのリストとリスト [X] との連結であれば, X は L の最後の要素です.

    last(L, X) :- append(_, [X], L).
また,与えられたリスト L の任意の要素 X を求める プログラム memb(X, L) は次のように書けます. つまり,リスト L が何かのリストとリスト [X|_] との連結であれば, X は L の要素です.

    memb(X, L) :- append(_, [X|_], L).

    | ?- memb(X, [a,b,c]).
    X = a ? ;
    X = b ? ;
    X = c ? ;
    | ?- append(W, [X|Y], [a,b,c]).
    W = [],
    X = a,
    Y = [b,c] ? ;
    W = [a],
    X = b,
    Y = [c] ? ;
    W = [a,b],
    X = c,
    Y = [] ? ;
    no
リストの要素を求めるプログラムは直接次のように書くこともできます.

    member(X, [X|_]).
    member(X, [_|L]) :- member(X, L).
次に,与えられた 2 つのリスト中に共通に含まれる要素だけから なるリストを求めるプログラムを書いてみましょう. たとえば [a,b,c] と [b,a,d,e] の共通リストは [a,b] です.

    common([], _, []).
    common([X|L], M, [X|L1]) :-
        member(X, M),
        !,
        common(L, M, L1).
    common([_|L], M, L1) :-
        common(L, M, L1).
各規則は次のような処理を表しています.
  1. 空リストとの共通リストは空リストである.
  2. X が M の要素の場合,リスト [X|L] と M の共通リストは, L と M の共通リストの前に X を付け加えたものである.
  3. X が M の要素でない場合,リスト [X|L] と M の共通リストは, L と M の共通リストである.
2 つ目の規則で member(X, M) が成功した場合, カット(!)の実行により, バックトラックが起こっても 3 つ目の規則は実行されません. つまり 3 つ目の規則は member(X, M) が失敗した場合にのみ実行されます. したがって 3 つ目の規則は X が M の要素でない場合に対応しているわけです.

プログラム reverse

与えられたリストを逆順に並べ換えるプログラムを書いてみましょう. この問題は次のように再帰的に考えることができます.
  1. 空リストの逆順は空リストである.
  2. リスト [X|L] の逆順は, L の逆順が R1 ならば, R1 の最後に X を付け加えたリストである.
これを Prolog でプログラムすると以下のようになります.

    reverse([], []).
    reverse([X|L], R) :-
        reverse(L, R1),
        append(R1, [X], R).
実行して見ると以下のようになります.

    | ?- reverse([a,b,c], R).
    R = [c,b,a] ? 
    | ?- reverse([[a,b],c,[d,e]], R).
    R = [[d,e],c,[a,b]] ? 
リストの中の要素までは逆順にならないことに注意して下さい.

補足説明: リストの逆順を求めるのは,以下のほうがより効率よいプログラムです.


    rev(L, R) :- rev(L, [], R).

    rev([], R, R).
    rev([X|L], Y, R) :- rev(L, [X|Y], R).
reverse を使うと, 与えられたリストが パリンドローム(回文)になっているかどうかを チェックするプログラムを簡単に書けます.

    palindrome(L) :- reverse(L, L).

    | ?- palindrome(['た','け','や','ぶ','や','け','た']).
    yes

プログラム permutation

与えられたリストの順序を並べ換えたリスト(順列)を求めるプログラムを 書いてみましょう. この問題は次のように再帰的に考えることができます.
  1. 空リストの順列は空リストである.
  2. 空でないリスト L の順列は, L から要素 X を取り除いたリストを L1 とし, L1 の順列を L2 としたとき, L2 の先頭に X を付け加えたリストである.
これを Prolog でプログラムすると以下のようになります.

    permutation([], []).
    permutation(L, [X|L2]) :-
        del(X, L, L1),
        permutation(L1, L2).

    del(X, [X|L], L).
    del(X, [Y|L], [Y|L1]) :-
        del(X, L, L1).
実行して見ると以下のようになります.

    | ?- permutation([1,2,3,4], X), write(X), nl, fail.
    [1,2,3,4]
    [1,2,4,3]
    [1,3,2,4]
    [1,3,4,2]
    [1,4,2,3]
    [1,4,3,2]
    [2,1,3,4]
    [2,1,4,3]
    [2,3,1,4]
    [2,3,4,1]
    [2,4,1,3]
    [2,4,3,1]
    [3,1,2,4]
    [3,1,4,2]
    [3,2,1,4]
    [3,2,4,1]
    [3,4,1,2]
    [3,4,2,1]
    [4,1,2,3]
    [4,1,3,2]
    [4,2,1,3]
    [4,2,3,1]
    [4,3,1,2]
    [4,3,2,1]
    no

プログラム sort

与えられたリストを昇順に並べ換えたリスト(整列)を求めるプログラムを 書いてみましょう. この問題は次のように考えることができます.
  1. 与えられたリストの順列であって, 昇順に並んでいれば,それは整列である.
これを Prolog でプログラムすると以下のようになります.

    slow_sort(L, L1) :-
        permutation(L, L1),
        ordered(L1).

    ordered([]).            % 空リストは昇順に並んでいる
    ordered([_]).           % 長さ1のリストも昇順に並んでいる
    ordered([X,Y|L]) :-     % 長さ2以上のリストは
	X =< Y,             % 先頭の2つが昇順で,
        ordered([Y|L]).     % 先頭を除いたリストが昇順なら,昇順
実行して見ると以下のようになります.

    | ?- slow_sort([3,1,4,2], X).
    X = [1,2,3,4] ? 
    yes
上のプログラムは,長さ n のリストに対して,n! の計算時間がかかります. では,「アルゴリズムとデータ構造」で勉強したクイックソートの プログラムを作りましょう. クイックソートのアルゴリズムは以下の通りです. これを Prolog でプログラムすると以下のようになります.

    qsort([], []).
    qsort([X|L], S) :-
        partition(L, X, L1, L2),
        qsort(L1, S1),
        qsort(L2, S2),
        append(S1, [X|S2], S).

    partition([], _, [], []).
    partition([Y|L], X, [Y|L1], L2) :-
        Y < X,
        partition(L, X, L1, L2).
    partition([Y|L], X, L1, [Y|L2]) :-
        Y >= X,
        partition(L, X, L1, L2).
SICStus Prologの組み込み述語 sort の場合, ソートした結果中で重複している要素は取り除かれます.

    | ?- sort([3,1,4,1,5,9], X).
    X = [1,3,4,5,9] ? 
    | ?- qsort([3,1,4,1,5,9], X).
    X = [1,1,3,4,5,9] ? 

リストから要素を選び出す

与えられたリスト中から,ある条件を満たすものだけを選び出す プログラムを作ってみましょう. たとえば,与えられたリスト L から正の数だけを選び出すことを考えます.

この問題を再帰的に考えると以下のようになります.

  1. L が空リストのとき, 答は空リスト.
  2. L が空リストでないとき,すなわち [X|L1] の形のとき, L1 から正の数だけを選び出したリストを L2 とすると, X が正なら答は [X|L2],そうでないなら答は L2.

これを Prolog でプログラミングしてみると次のようになります.


    pos([], []).
    pos([X|L1], [X|L2]) :-
        X > 0,
        !,			% X > 0 なら下の規則は調べない
        pos(L1, L2).
    pos([X|L1], L2) :-		% X > 0 でない場合
        pos(L1, L2).
記号 ! (カット) の意味については,教科書を参照してください.

練習問題

問題5
与えられたリスト L の要素の合計 S を求める述語 sum_list(L,S) を定義しなさい.
問題6
与えられたリスト L 中で N 以上の要素だけを集めた リスト M を求める述語 ge_list(L,N,M) を定義しなさい. たとえば ?- ge_list([3,1,4,1,5,9],4,M). の結果は M = [4,5,9] です.

最初に戻る 前へ 次へ