Matching tuples in Prolog

Question

Why does Prolog match (X, Xs) with a tuple containing more elements? An example:

test2((X, Xs)) :- write(X), nl, test2(Xs).                                    
test2((X)) :- write(X), nl.                                                   

test :-                                                                       
        read(W),                                                               
        test2(W). 

?- test.
|: a, b(c), d(e(f)), g.
a
b(c)
d(e(f))
g
yes

Actually this is what I want to achieve but it seems suspicious. Is there any other way to treat a conjunction of terms as a list in Prolog?

Answer 1

Hmm... a, b(c), d(e(f)), g means a and (b(c) and (d(e(f)) and g)), as well list [1,2,3] is just a [1 | [2 | [3 | []]]]. I.e. if you turn that conjuction to a list you'll get the same test2([X|Xs]):-..., but difference is that conjunction carries information about how that two goals is combined (there may be disjunction (X; Xs) as well). And you can construct other hierarchy of conjunctions by (a, b(c)), (d(e(f)), g)

You work with simple recursive types. In other languages lists is also recursive types but they often is pretending to be arrays (big-big tuples with nice indexing).

Probably you should use:

test2((X, Y)):- test2(X), nl, test2(Y).
test2((X; Y)). % TODO: handle disjunction
test2(X) :- write(X), nl.

Answer 2

Tuple term construction with the ,/2 operator is generally right-associative in PROLOG (typically referred to as a sequence), so your input of a, b(c), d(e(f)), g might well actually be the term (a, (b(c), (d(e(f)), g))). This is evidenced by the fact that your predicate test2/1 printed what is shown in your question, where on the first invocation of the first clause of test2/1, X matched a and Xs matched (b(c), (d(e(f)), g)), then on the second invocation X matched b(c) and Xs matched (d(e(f)), g), and so on.

If you really wanted to deal with a list of terms interpreted as a conjunction, you could have used the following:

test2([X|Xs]) :- write(X), nl, test2(Xs).                                    
test2([]).

...on input [a, b(c), d(e(f)), g]. The list structure here is generally interpreted a little differently from tuples constructed with ,/2 (as, at least in SWI-PROLOG, such structures are syntactic sugar for dealing with terms constructed with ./2 in much the same way as you'd construct sequences or tuple terms with ,/2). This way, you get the benefits of the support of list terms, if you can allow list terms to be interpreted as conjunctions in your code. Another alternative is to declare and use your own (perhaps infix operator) for conjunction, such as &/2, which you could declare as:

:- op(500, yfx, &). % conjunction constructor

You could then construct your conjunct as a & b(c) & d(e(f)) & g and deal with it appropriately from there, knowing exactly what you mean by &/2 - conjunction.

See the manual page for op/3 in SWI-PROLOG for more details - if you're not using SWI, I presume there should be a similar predicate in whatever PROLOG implementation your'e using -- if it's worth it's salt :-)

EDIT: To convert a tuple term constructed using ,/2 to a list, you could use something like the following:

conjunct_to_list((A,B), L) :-
  !,
  conjunct_to_list(A, L0),
  conjunct_to_list(B, L1),
  append(L0, L1, L).
conjunct_to_list(A, [A]).