自然数のリスト

ある数未満の自然数すべてを 要素とするリストを作るような述語は, 以下のように書ける.

naturals(N,M,List) :- N>=M | List=[].
naturals(N,M,List) :- N<M  | List=[N|Rest], N1:=N+1, naturals(N1,M,Rest).

naturals(M,List) :- naturals(0,M,List).

最初のふたつの節で定義する述語は, 第1引数の値から始めて, 第2引数未満の 整数すべてを小さい順に要素に持つリストを, 第3引数に返すものである. 最 初の節は, 第1引数が第2引数より小さくなければ, 空のリストを返せば良い, という意味である. 次の節は, 第1引数の方が小さければ, 第1引数を先頭要 素とするリストを返せば良く, リストの残り部分は第1引数よりひとつだけ大 きい値から始めて第2引数未満の整数すべてを小さい順に要素に持つリストに すれば良い, という意味である.

最後の節で本来定義したかった述語を定義していて, 3引数の方の述語を 0 か ら始めるように呼べば, 与えられた引数未満の自然数すべてを要素にするリス トが作れる, ということを書いてあるわけだ.

この例でも, ふたつめの節のボディにある, ユニフィケーション, 足し算, 再 帰呼び出しの三者は, どんな順で実行しても (並列に実行しても) 構わない.