Menu
I'm trying to write a predicate twice(El,L) which will return true. when El is on list exactly twice. Here is what I have:
twice(El,L) :- select(El,L,L1), member(El,L1), \+ twice(El,L1).
It works nice for twice(2,[1,2,2,3,4])
but for twice(X,[1,1,2,2,3,3]) it doubles every number X = 1 ; X = 1 ; X = 2... How could I avoid this without using any accumulator?
438
To sum the elements in a list inductively, we add the first element to the sum of the remaining ones. In Prolog we say this: sum([H|T], S) :- sum(T,X), S is H + X. Another common pattern in Prolog is tail-recursion, which is popular because it's easy for the compiler to optimize.
In prolog, lists have got only one operator, called pipe, denoted by |. This operator is used to append an element at the beginning of a list. The syntax of the pipe operator is as follows : [a | L] Here L is a list and a is a single element. For example: If, L = [b,c,d] Then, [a | L] will result in [a,b,c,d]
In Prolog list elements are enclosed by brackets and separated by commas. Another way to represent a list is to use the head/tail notation [H|T]. Here the head of the list, H, is separated from the tail of the list, T, by a vertical bar. The tail of a list is the original list with its first element removed.
You want to describe a sequence of elements. For such, there is a special formalism in Prolog called Definite Clause Grammars. Before using the formalism, let's try to figure out how a sequence with E occurring exactly twice looks like:
E
E
E
E
E.Now, to put this into the DCG formalism
twice(E, L) :-
phrase(twice_occurring(E), L). % Interface
twice_occurring(E) -->
seq_without(E), % 1.
[E], % 2.
seq_without(E), % 3.
[E], % 4.
seq_without(E). % 5.
seq_without(_E) -->
[].
seq_without(E) -->
[X],
{dif(X,E)},
seq_without(E).
Or, more compactly by using all//1 and avoiding auxiliary definitions:
twice(E, L) :-
phrase(( all(dif(E)), [E], all(dif(E)), [E], all(dif(E)) ), L).
There is essentially only one drawback with these definitions: On current systems, they are not optimally implemented. See this if you want to know more.
80
Stay both logically pure and efficient by using if_/3 and
(=)/3 by @false. It goes like this:
list_member1x([X|Xs],E) :-
if_(X=E, maplist(dif(E),Xs), list_member1x(Xs,E)).
list_member2x([X|Xs],E) :-
if_(X=E, list_member1x(Xs,E), list_member2x(Xs,E)).
twice(E,Xs) :-
list_member2x(Xs,E).
That's it. Let's run some queries!
?- twice(E,[1,2,3,4,5,2,3,4]).
E = 2 ;
E = 3 ;
E = 4 ;
false.
Now something a little more general:
?- twice(X,[A,B,C,D]).
A=X , B=X , dif(C,X), dif(D,X) ;
A=X , dif(B,X), C=X , dif(D,X) ;
A=X , dif(B,X), dif(C,X), D=X ;
dif(A,X), B=X , C=X , dif(D,X) ;
dif(A,X), B=X , dif(C,X), D=X ;
dif(A,X), dif(B,X), C=X , D=X ;
false.
Here are the queries the OP gave:
?- twice(2,[1,2,2,3,4]).
true.
?- twice(E,[1,1,2,2,3,3]).
E = 1 ;
E = 2 ;
E = 3 ;
false.
As an alternative, use meta-predicate tcount/3 in combination with (=)/3 like this:
twice(E,Xs) :- tcount(=(E),Xs,2).
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
