きくらげ観察日記

好きなことを、適当に。

Prologならではのソートアルゴリズム

簡単な問題なら問題をPrologの言葉で書いてやるだけで勝手に解けてしまうのが、Prologのすごい所です。
例えばソートに関しても、(計算量とかの話に目を瞑ってしまえば)こんなに簡単に書くことができるようになります。

% sort.pl

% remove(X, L, M) : リスト L から要素 X を先頭から1つ削除したものが M である
remove(X, [X | L], L).
remove(X, [Y | L], M) :-
    remove(X, L, N),
    M = [Y | N].

% perm(L, M) : リスト L を並べ替えたものがリスト M である
perm([], []).
perm(L, [X | M]) :-
    remove(X, L, L1),
    perm(L1, M).

% sorted(L) : リスト L はソート済みである
sorted([]).
sorted([X]).
sorted([X, Y | L]) :-
    X =< Y,
    sorted([Y | L]).

% lsort(L, M) : M は L をソートしたものである
lsort(L, M) :-
    perm(L, M),
    sorted(M),
    !.

Prologを知らない人のために簡単に説明すると、このコードは

MがLをソートしたものであるとは、
    MはLを並べ替えたもので、
    Mの各要素は昇順に並べられている
ということである。

という定義を行っただけです。Prologの場合、これがソートアルゴリズムそのものとなります。

実行結果:

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

?- lsort([3, 2, 5, 10, 4, 2, 3, 0], L).
L = [0, 2, 2, 3, 3, 4, 5, 10].

?- lsort([], L).
L = [].