2007-11-04

Prolog (5)

前回に引き続きリスト系のユーティリティ述語の紹介です。

fold(l/r)を定義したら当然のことですがunfoldが定義したくなりますね?幸いにもPrologはバックトラックがありますから、特に遅延評価のための仕組みを用意せずとも、Haskellのようにunfoldを書くことが出来ます。しかしその前にもっと細かいユーティリティを定義しておきます。

まずはリストの最後の要素を取得するlast/2です。

% last/2
last([X], X).
last([_|R], X) :- last(R, X).

?- last([1, 2, 3], X).
X = 3


続いてリストの最後以外の部分を取得するunlast/2です。

% unlast/2
unlast(L, R) :-
last(L, Y),
append(R, [Y], L).

?- unlast([1, 2, 3], L).
L = [1, 2]

個人的にはこの述語なんか簡単で、如何にも宣言的な書き方かなぁと思っています。二つ目のゴールで最後の要素を後ろに付けたリストが元のリストだと宣言してるわけですね。

さてリストのN番目の要素を取得するnth/3はこんな感じ。

% nth/3
nth(1, [X|_], X).
nth(N, [_|R], X) :- N > 1, N1 is N - 1, nth(N1, R, X).

?- nth([1, 2, 3], 2, X).
X = 2


ところで引数の並びをどうするかというのは悩みどころです。特に高階述語を書く場合は、与える引数の位置が重要ですからね。そこで自分の中でルールを決めておくという手もあるのですが、順番を変えたい場合はチェインというのを定義してやります。

% last1/2
last1(X, L) :- last(L, X).

上のlast1/2ではlastを呼び出すことしかしません。ただし引数を並び替えています。このようにエイリアスのような役目をする述語を(慣用的に)チェインと呼びます。

それではunfold/4を定義してみましょう。

% unfold/4
unfold(Fn, X, L, L1) :-
last(L, Y),
G =.. [Fn, X, Y, Y1],
call(G),
append(L, [Y1], L1).
unfold(Fn, X, L, L2) :-
last(L, Y),
unfold(Fn, X, L, L1),
unfold(Fn, Y, L1, L2).

?- nth(10, L, X), unfold(plus, 0, [1], L).
L = [1, 1, 2, 3, 5, 8, 13, 21, 34|...],
X = 55

出来ました。ちなみにnth/3を使っている理由はもうすでにお気づきですね?それではunfold/4単体でフィボナッチ数を計算してみましょう。

?- unfold(plus, 0, [1], L).
L = [1, 1] ;
L = [1, 1, 2] ;
L = [1, 1, 2, 3] ;
L = [1, 1, 2, 3, 5] ;
...

ご覧の様に、別の解を要求する度にリストが伸びて計算を行っていきます。上の例ではnth/3でリストの幾つ目の要素が欲しいのかを条件として与えていますから、それを満たすリスト長になるまでバックトラックを起こして次の値を計算しているわけです。

0 件のコメント: