Sortowanie

WEJŚCIE:

:-sort(cons(z, cons(s(z), cons(z, cons(s(s(z)), nil)))), X).

WYJŚCIE:

X -> cons(z, cons(z, cons(s(z), cons(s(s(z)), nil))))

ROZWIĄZANIE:

sort(nil, nil).

sort(cons(X, nil), cons(X, nil)).

sort(cons(A, cons(B, C)), Sorted):-

split(cons(A, cons(B, C)), L1, L2),

sort(L1, S1),

sort(L2, S2),

merge(S1, S2, Sorted).

split(cons(A,B), cons(A,C), L2):-

split(B, L2, C).

split(nil, nil, nil).

merge(nil, S, S).

merge(cons(A, B), nil, cons(A, B)).

merge(cons(A, B), cons(C, D), cons(A, F)):-

lt(A, C),

merge(B, cons(C, D) , F).

merge(cons(A, B), cons(C, D), cons(C, F)):-

leq(C, A),

merge(cons(A, B), D, F).

lt(s(X), s(Y)):-lt(X, Y).

lt(z, s(X)).

leq(s(X), s(Y)):-leq(X, Y).

leq(z, X).