Prolog XOR on elements of list

Question

I am new in Prolog and I would like to apply XOR operation on elements of given list of length n. The predicate should return True if list contains some false elements in the first n-1 element or if last element is True.

I have written the following code so far, but it does not work properly such as for the query ?- function([true,false,false]) the predicate should return True but it returns false.

function([X|_]) :-  \ + X,!.
function([X]):-X,!.
function([_|XS]):- function(XS),!,helper(XS).

helper([X]):- X,!.
helper([_|YS]):- helper(YS),!.

I would appreciate if you could help me. Thanks!

"The predicate should return True if list contains false in the first n-1 element or if last element is True." - please clarify what does XOR-ing a list mean, according to that description [true, false, false] should return false(first n-1 elements are not all false, last element is false) — Ventsyslav Raikov, Jun 27 '15 at 12:33

score 1 · Accepted Answer · edited May 23 '17 at 12:06

Here's your spec again:

The predicate should return True if list contains some false elements in the first n-1 element or if last element is True.

Let's define predicate xor_check/1 like this:

xor_check(List) :-
   booleans(List),
   append(ButLast,[Last],List),
   xor_check__aux(Last,ButLast).

Above code is based on xor_check__aux/2, which in turn builds on memberd/2:

xor_check__aux(true,_).
xor_check__aux(false,ButLast) :-
   memberd(false,ButLast).

The auxiliary predicates boolean/1 and booleans/1 can be defined as:

boolean(true).
boolean(false).

booleans([]).
booleans([B|Bs]) :-
   boolean(B),
   booleans(Bs).

Sample queries (with SICStus Prolog 4.3.2):

?- xor_check([true,false]).
no
?- xor_check([true,true,true]).
yes
?- xor_check([true,false,false]).
yes

Please note that the toplevel of SICStus Prolog does not show the choicepoints left open by `member/2`. `memberd/2` would be preferable. Also, there is no need for the `->` — false, Jun 28 '15 at 06:43

score 1 · Answer 2 · answered Jun 29 '15 at 17:44

A XOR B if true if either A or B is true, but not both. Here's its truth table:

  A   |   B   | A XOR B
------+------ |---------
false | false | false
false | true  | true
true  | false | true
true  | true  | false

Write that truth table as a Prolog predicate:

%      A       B   | A XOR B
%    -----   ----- | -------
xor( false , false , false   ) .
xor( false , true  , true    ) .
xor( true  , false , true    ) .
xor( true  , true  , false   ) .

Then it's a simply mater of recursively it over the list. When the list collapsed to a single element, it succeeds on [true] and fails otherwise:

xor_list( [ A,B | T ] ) :- xor(A,B,C) , xor_list( [C|T] ) .
xor_list( [ true    ] ) .

This can all be collapsed into a slightly smaller/simpler predicate:

xor_list( [ false , false | T ] ) :- xor_list( [ false | T ] ) .
xor_list( [ false , true  | T ] ) :- xor_list( [ true  | T ] ) .
xor_list( [ true  , false | T ] ) :- xor_list( [ true  | T ] ) .
xor_list( [ true  , true  | T ] ) :- xor_list( [ false | T ] ) .
xor_list( [ true              ] ) .

score -2 · Answer 3 · answered Jun 27 '15 at 12:43

-2

I don't have a prolog compiler at hand but this should do the trick.

function([false|_]).

function([X]):- X.

function([_ | XS]) :- function(XS).

answered Jun 27 '15 at 12:43

Ventsyslav Raikov

6,882
1
25
28

Thank you for reply. But it also does not work properly for example the query ?-function([true,false]) should return false because there exists no false element in the first n-1 elements (1 ≤ i < n) or the last element is also not true. – user3074510 Jun 27 '15 at 12:55

Prolog XOR on elements of list

3 Answers3