Sublistic predicate in Prolog
I am trying to define a predicate sublist(X,Y)
in Prolog that is true when the elements of a list X
all appear in the list Y
, in the same order as in X
.
My approach is to take the head X
, find the first instance of the head in Y
and cut out the list just before that first instance, and then repeat this with the tail X
until the tail equals the empty list.
I wrote a helper predicate cut(X,Y,Z)
that evaluates to true if it Z
is the resulting list of all objects before the first instance X
in the list Y
.
My code looks like this:
cut(_,[],[_|_]) :- false.
cut(X,[H|T],[H|T]) :- X = H, !.
cut(X,[_|T],Y) :- cut(X,T,Y).
sublist([],[]).
sublist([],[_|_]).
sublist([A|B],C) :- cut(A,C,Z), sublist(B,Z).
When I request
?- sublist(L,[1,2,3]).
Instead of giving all sublists, [1,2,3]
Prolog gives me the following output:
L = [] ;
L = [1] ;
L = [1, 1] ;
L = [1, 1, 1] ;
L = [1, 1, 1, 1] ;
L = [1, 1, 1, 1, 1] ;
L = [1, 1, 1, 1, 1, 1] ;
L = [1, 1, 1, 1, 1, 1, 1] ;
L = [1, 1, 1, 1, 1, 1, 1, 1] ;
L = [1, 1, 1, 1, 1, 1, 1, 1, 1] ;
L = [1, 1, 1, 1, 1, 1, 1, 1, 1|...] ;
L = [1, 1, 1, 1, 1, 1, 1, 1, 1|...] ;
L = [1, 1, 1, 1, 1, 1, 1, 1, 1|...]
I don't see my mistake. Can anyone point me to this?
source to share
Short answer : cut/3
contains no pop from the list if it finds an element.
The first answer L = [].
is the result of shelling the second sentence. Now the next response is generated by the last sentence. So what's going on:
sublist(A,[1,2,3]) :- % C = [1,2,3]
cut([A|B],[1,2,3],[H|T]) :- % H = 1, T = [2,3], Z = [1,2,3]
A = H, % A=1
!.
sublist(B,[1,2,3]).
So, since the second clause cut/3
fires, the second and third arguments are equivalent and therefore cut/3
does not "pop" from the list .
In this list, there is a way to solve this problem and ensure progression:
cut(_,[],[_|_]) :- false.
cut(H,[H|T],T) :-
!.
cut(X,[_|T],Y) :-
cut(X,T,Y).
(I also took the liberty of replacing X
with H
in the sentence chapter, making it more elegant.) Now it generates:
?- sublist(L,[1,2,3]). L = [] ; L = [1] ; L = [1, 2] ; L = [1, 2, 3] ; false.
Note that the answer does not generate all the lists: for example, L = [2,3]
it is also a valid answer. The reason this doesn't work is because it cut/3
has !
and therefore does not allow for additional elements to be introduced. You can solve this problem with
cut(_,[],[_|_]) :- false.
cut(H,[H|T],T).
cut(X,[_|T],Y) :-
cut(X,T,Y).
Now we get:
?- sublist(L,[1,2,3]). L = [] ; L = [1] ; L = [1, 2] ; L = [1, 2, 3] ; L = [1, 3] ; L = [2] ; L = [2, 3] ; L = [3] ; false.
However, you can solve the problem quite elegantly by not using a help predicate at all. We can first build a predicate that checks / creates lists:
list([]).
list([_|T]) :-
list(T).
Next, we'll indicate that if X
empty, you don't care which list is on the right:
sublist([],L) :-
list(L).
And finally, if X
not empty, we need to get HX
(chapter X
) somewhere. If we find it, we can either accept it, or put both lists, or we can choose another HX
, for example:
sublist([HX|TX],[HX|TY]) :-
sublist(TX,TY).
sublist(X,[_|TY]) :-
X = [_|_],
sublist(X,TY).
X = [_|_]
in the last section is not strictly necessary, but it does not allow you to generate duplicate results using a sentence sublist([],X)
.
Or connect it:
list([]).
list([_|T]) :-
list(T).
sublist([],L) :-
list(L).
sublist([HX|TX],[HX|TY]) :-
sublist(TX,TY).
sublist(X,[_|TY]) :-
X = [_|_],
sublist(X,TY).
This generates:
?- sublist(L,[1,2,3]). L = [] ; L = [1] ; L = [1, 2] ; L = [1, 2, 3] ; L = [1, 3] ; L = [2] ; L = [2, 3] ; L = [3] ; false.
Or:
?- sublist([1,2,3],L). L = [1, 2, 3] ; L = [1, 2, 3, _G2440] ; L = [1, 2, 3, _G2440, _G2443] ; L = [1, 2, 3, _G2440, _G2443, _G2446] ; L = [1, 2, 3, _G2440, _G2443, _G2446, _G2449] ; L = [1, 2, 3, _G2440, _G2443, _G2446, _G2449, _G2452] ; L = [1, 2, 3, _G2440, _G2443, _G2446, _G2449, _G2452, _G2455] ; L = [1, 2, 3, _G2440, _G2443, _G2446, _G2449, _G2452, _G2455|...] ;
Or:
?- sublist([1,2,3],[1,2,4,5,3,6]).
true ;
source to share