sum([]) :- 0;
sum([X|Y]) :- X + sum(Y);

append([], Z) :- Z;
append([X|Y], Z) :- [X | append(Y, Z)];

reverse([]) :- [];
reverse([X|Y]) :- append(reverse(Y), [X]);

fastrev(X) :- fastrev1(X, []);

fastrev1([], X) :- X;
fastrev1([X|Y], Z) :- fastrev1(Y, [X|Z]);



prefix([], X);
prefix([X|Y], [X|Z]) :- prefix(Y, Z);

sublist(List1, List2) :- prefix(List1, List2), 1;
sublist(List1, [_|List2]) :- 1+sublist(List1, List2);

insert(N, []) :- [N];
insert(N, [M | Rest]) :- N <= M, [N, M | Rest];
insert(N, [M | Rest]) :- [M| insert(N, Rest)];

sort([]) :- [];
sort([N|Rest]) :- insert(N, sort(Rest));