Understanding the append syntax

Question

I am having some trouble understanding this piece of code.

powerset(L, [H|T]):-
  append([H|T], _, L).

It originates from this thread and does exactly what I want; however, I would also like to understand the code that I am using.

Answer 1

Let us first consider the clause's single goal in isolation:

?- append([H|T], _, L).

What does this mean? With pure Prolog code, there is a good and convenient way to learn more about relations: Simply post a query on the toplevel and see what solutions look like.

Try it out! For example:

?- append([H|T], _, L).
L = [H|_1282],
T = [] ;
L = [H, _1078|_1096],
T = [_1078] ;
L = [H, _1078, _1084|_1108],
T = [_1078, _1084] ;
L = [H, _1078, _1084, _1090|_1120],
T = [_1078, _1084, _1090] ;
etc.

From this we see that this call of append/3 defines a relation between its arguments, and we see the following pattern:

L always consists of:

• H as the first element
• followed by all elements in T
• followed by a suffix.

This is not suprising, since that's exactly what append([H|Ts], _, Ls) means: [H|Ts] followed by any list at all constitutes the list Ls.

In your concrete use case, it is obvious that L is meant to be instantiated, and so the suffix cannot be arbitrarily long.

For example:

?- append([H|T], _, [a,b,c]).
H = a,
T = [] ;
H = a,
T = [b] ;
H = a,
T = [b, c] ;
false.

And so we see the meaning of the whole clause (I have renamed the variables so that lists are denoted by the suffix s in variable names):

powerset(Ls, [H|Ts]):-
    append([H|Ts], _, Ls).

If Ls is a list that contains as its first element H, followed by elements Ts, followed by anything at all, then the list [H|Ts] is a member of the powerset of L.

Informally:

Every nonempty prefix of the list is a member of the powerset.

And from this we also see a glaring omission of powerset/2 as it appears in this thread: None of the clauses yields the empty set as a member of the powerset, and even more disturbingly, none of them accepts the empty set as a valid set, so the following incorrectly fails:

?- powerset([], _).
false. % empty set is not a set?

Exercise: Correct powerset/2 so that it actually succeeds for all elements of the powerset.