Prolog 写経記 その 58 min/2

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

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

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

解説

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

ふむ．

モード

min(+, ?).

ふむふむ．

定義

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

min([X], X) :-
	!.
min([X | List], X) :-
	min(List, Min),
	X < Min, !.
min([_ | List], Min) :-
	min(List, Min), !.

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

注記

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

ふむふむふむふむ．

例

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

2 ?- min([-2.1, 11.5, -7.0], X).

X = -7.0 

Yes
3 ?- min([], MinElement).

No

ふむふむふむふむふむ．

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

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

min([X], X) :-
	!.
min([X | List], Min) :-
	min(List, Min1),
	X >= Min1, !,
	Min = Min1.
min([X | _], X) :-
	!.

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

min([X | List], Min) :-
	min(List, Min),
	X >= Min, !.

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

5 ?- min([-2.1, 11.5, -7.0], X).

X = -7.0 

Yes
6 ?- min([], MinElement).

No

いい感じ♪

---