Compare two lists = if sublist of a list = true

Help!
1

I want to define a function in Prolog, which is able to compare two lists and if it is a sublist of the second list than give true as output.

My solution is this:

foo1([],[RL2]).
foo1([],[]).
foo1([E|RL], [E2|RL2]) :-
	 E = E2 -> 
	foo1(RL,RL2);
	foo1([E|RL],RL2),
	foo1([],[RL2]).

The Problem is, that I need true if it is [] or if there is a restlist.

Because if it is foo1([1,2],[1,2,3]). //it should be true
and if foo1([1,2],[1,2]). //it should be also true

But in my case it is true or false. Please help, there must be an easy solution.

2

Oh good, you reformatted it.

The way to solve such a problem in Prolog is to write out your thinking logically in English.

A is a sublist of B if:
A is empty, or
The first letter of A and B are the same and…

Once you have the English version you can very quickly substitute English for Prolog symbols and it will work exactly the same.

3

No it is not absolute necassary that the first Letter of A and B are the same.

for example
foo1([1,2],[4,1,2,3]). //should also be true

4

I’m not solving it for you. I’m asking you to write out the rules in English, and then expand into logical reasoning about those rules.

1 Like
5

An alternative way of thinking about the problem is to define a “mathematical” specification of what it means for one list to be a sublist of another.

For example, A is a sublist of B if B can be broken into a “before”, “middle”, and “after” (any of which can be empty), and A is equal to one of these. In Python, I can test this as follows:

>>> a = [2,3,4]
>>> b = [1,2,3,4,5,6]
>>> before = [1]
>>> after = [5,6]
>>> before + a + after == b  # tests: "a is sublist of b"
True
>>> b = [2,3,4,5,6]
>>> before = []
>>> after = [5,6]
>>> before + a + after == b  # tests: "a is sublist of b"
True
6

Thank you for your effort but I still don´t get it.
But first of all. The last fact was wrong. So without it it is “right”

foo1([],[RL2]).
foo1([],[]).
foo1([E|RL], [E2|RL2]) :-
E = E2 ->
foo1(RL,RL2);
foo1([E|RL],RL2).

So: First I compare the first element of the first list and the second list. If they are equal, I do the same with the restlist. If it isn´t the same I still take the first element of the first list and compare it to the rest oft the second list. It ends if the first list ist empty. And gives out true if the first list is empty and the second list or the second list is still filled with elements.

7

Think about what these two clauses mean:

foo1([],[RL2]).
foo1([],[]).

If we read foo1(X,Y) as “X is a subset of Y”, then the 1st clause means “the empty list is a subset of a list containing one element” and the 2nd clause means “the empty list is a subset of the empty list”.

You probably want to say something different: “the empty list is a subset of …”.

(Your last clause can be read “X is a subset of Y if the first element of X is the same as the first element of Y and the rest of X is a subset of the rest of Y; or if X is a subset of the rest of Y”.)

2 Likes
8

The easy solution is probably to use append/3. From the examples it seems you really want a sublist (not a subsequence). As Peter above tried to explain:

list_sublist(L, S) :-
    append(_Prefix, Rest, L),
    append(S, _Suffix, Rest).

It’s one of those “look ma no hands” Prolog examples.

1 Like
9

One of the games you can play with Prolog is "how can I write this predicate using only append/3"? (These are sometimes efficient, sometimes not.)

For example:

fist(X, List) :- append([X], _, List).
last(X, List) :- append(_, [X], List).
member(X, List) :- append(_, [X|_], List).
select(X, List, Rest) :- append(Prefix, [X|Suffix], List), append(Prefix, Suffix, Rest).

etc.

2 Likes
10

Thank you very much for your help. I´m much smarter now.

I figured out, that my code is working if I implement an unattractive cut. Like that:
foo1([],[RL2]) :- !.
foo1([],[]).
foo1([E|RL], [E2|RL2]) :-
E = E2 ->
foo1(RL,RL2);
foo1([E|RL],RL2).

But the thinking about append is very helpful!

11

Your code fails this test:

foo1([1,2,3,4], [1,2,3,4,5,6,7]).

You need to think again about what the empty list is a subset of.