Prolog 写経記 その 56 max/2

(ほぼ) 毎日淡々と Prolog を写経します．元ネタはこちら．

Prologユーティリティライブラリ

今日は max/2 を写経します．

解説

max(Numlist, Max) は数のリスト Numlist 中の最大値を返すか，あるいは Max が Numlist 中で最大の数かどうかを調べる．

ふむ．

モード

max(+, ?).

ふむふむ．

定義

では，こいつの定義を写経しませう．

max([X], X) :-
	!.
max([X | List], X) :-
	max(List, Max),
	X > Max, !.
max([_ | List], Max) :-
	max(List, Max), !.

ふむふむふむ．
リストの要素が一つだけならそれが最大値．
リストの先頭の要素が残りの要素からなるリストの最大値よりも大きければそれが最大値．
そうでなければリストの 2 番目以降の要素からなるリストの最大値が全体の最大値．
らじゃあ．

注記

max/2 は Numlist が空リストの場合や，その要素が数でない場合は失敗する．max/2 をアトムのリストに適用するには，アルファベット比較演算子 age (3 章参照) を > の代わりに用いるとよい．

ふむふむふむふむ．

例

では使用例を写経しませう．

2 ?- max([255, 713, 23, 521, 4], X).

X = 713 

Yes
3 ?- max([255, 713, 23, 521, 4], 255).

No

ふむふむふむふむふむ．

この定義，結果が正しいのは分かるのですがあまり効率的には見えませんね．
気に入らないのは，リストの先頭の要素が最大値でない場合に 2 番目の節と 3 番目の節で全く同じ再帰呼び出しを行うこと．
そんなの，明らかに
無駄無駄無駄無駄無駄無駄無駄無駄無駄無駄無駄無駄無駄無駄無駄無駄無駄無駄無駄無駄無駄無駄無駄ぁぁぁぁぁぁぁぁぁぁ〜〜〜〜〜〜〜〜〜〜
ですから！！ 残念！！！！

そんなわけで (どんなわけで？)，再帰呼び出しを一回だけで済ませることにしましょう．
再帰呼び出しで2番目以降の要素中の最大値が先頭の要素よりも小さければ，先頭の要素が最大値に決まってるったら決まってます．
なので，

max([X], X) :-
	!.
max([X | List], Max) :-
	max(List, Max1),
	X =< Max1, !,
	Max = Max1.
max([X | _], X) :-
	!.

ってことになりました．
2 番目の節で

max([X | List], Max) :-
	max(List, Max),
	X =< Max, !.

としないでちょっと回りくどいことをしているのは，第 2 引数にリストの最大値と異なる具体的な数値を渡された場合に 3 番目の節へ進んでしまうのを防ぐため．
ともあれ (JW)，例をお試し．

7 ?- max([255, 713, 23, 521, 4], X).

X = 713 

Yes
8 ?- max([255, 713, 23, 521, 4], 255).

No

いい感じ♪

---