Mercury: Append Predicate - this demonstrates argument unification

append.m

%% this is a linked list append, which is O(n), because it needs to break up the list until the end, then add the list to be appended at the very end, then build up the list again by consing them!
%% unlike loops, each step is a recursion, and I guess there might some sort of tail call optimisation that makes sure that a stack doesn't grow forever in functional languages

:- pred append(list(T), list(T), list(T)).
:- mode append(in, in, out) is det.
:- mode append(out, out, in) is multi.

append(Xs, Ys, Zs) :-
    (
        Xs = [], Zs = Ys %% conjunction
        ; %% disjunction
        Xs = [X | Xs0], append(Xs0, Ys, Zs0), Zs = [X | Zs0] %% conjunction
    ).