Finding a specific sequence of elements in a list, prolog

Question

I have to write a predicate that takes a List and succeeds if the list contains elements "a, b, c"in that order anywhere in the list, other wise it fails. I am pretty lost on where to start(not looking for a solution, just a hint to the right direction).

Answer 1

Finding a,b,c

To find the letters a,b,c in a list in that order one should start with the comment by @lurker which says [X, Y, Z | T].

has_abc([a,b,c|T]).

Since I am using SWI-Prolog and prefer not to receive the warning

Warning: somecode.pl: Singleton variables: [T]

I will make a small change by changing T to _

has_abc([a,b,c|_]).

and then run some simple test

?- has_abc([a,b,c]).
true.

?- has_abc([a,b,c,z]).
true.

?- has_abc([z,a,b,c]).
false.

As you can see the predicate has_abc can find a,b,c at the start of a list but not any place else.

Taking a list a part

In Prolog a list can be recursively deconstructed using [H|T]

deconstruct_list([Head|Tail]) :- write('Head of list: '),write(Head),nl, deconstruct_list(Tail).

and a few demonstration cases

?- deconstruct_list([]).
false.

?- deconstruct_list([a]).
Head of list: a
false.

?- deconstruct_list([a,b]).
Head of list: a
Head of list: b
false.

?- deconstruct_list([a,b,c]).
Head of list: a
Head of list: b
Head of list: c
false.

Putting the predicates together

Now combining the first two predicates for finding a,b,c and deconstructing a list gives us

has_abc([a,b,c|_]).
has_abc([_|T]) :- has_abc(T).

and a few test cases

?- has_abc([]).
false.

?- has_abc([a]).
false.

?- has_abc([a,b]).
false.

?- has_abc([a,b,c]).
true .

?- has_abc([z,a,b,c]).
true .

?- has_abc([a,b,c,z]).
true .

?- has_abc([z,a,b,c,z]).
true .

Resolving the choice-point with a cut

Almost there. There is a small problem because for the true answers we had to press Enter to exit which indicates we have a choice-point.

A way to fix this is with a cut (!) which say that once we have an answer stop looking for more answers.

has_abc([a,b,c|_]) :- !.
has_abc([_|T]) :- has_abc(T).

and a few test cases

?- has_abc([]).
false.

?- has_abc([a]).
false.

?- has_abc([a,b]).
false.

?- has_abc([a,b,c]).
true.

?- has_abc([z,a,b,c]).
true.

?- has_abc([a,b,c,z]).
true.

?- has_abc([z,a,b,c,z]).
true.

?- has_abc([d]).
false.

?- has_abc([d,e]).
false.

?- has_abc([d,e,f]).
false.

?- has_abc([d,e,f,g]).
false.

Notice that when running the test cases one did not have to press Enter to end the query.

Resolving the choice-point without a cut

See the answer by mat

Answer 2

Another way to describe the relation uses a grammar. You are talking about a sequence, well, that's what the dcg formalism is for!

:- set_prolog_flag(double_quotes, chars).
abcsubsequence(Cs) :-
   phrase(abc, Cs).

abc -->
   ..., "abc", ... .

or alternatively, if you permit further text in between:

abc -->
   ..., "a", ..., "b", ..., "c", ... .

So what is this magic ...? It's just any sequence:

... --> [] | [_], ... .

Efficiency-wise mat's solution is much better. But for correctness reasons above versions are better since they fail for abcsequence([a,b,c|non_list]). However, making relations a tiny bit more general by permitting such solutions is quite common in Prolog, you just have to be aware of it.

Answer 3

Declarative wording

Almost always, when a Prolog task is formulated in a rather imperative way, the solution will be comparatively limited. This means that we typically can only use it in a few modes and directions, while other modes may even yield wrong results.

Therefore, I suggest to use more declarative wording.

You say:

a predicate that takes a list and succeeds if the list contains elements "a, b, c" in that order anywhere in the list, otherwise it fails.

That's a rather procedural way to look at this. Note that in Prolog, any argument can also be a logical variable, and thus there may not even be a list to "take". Instead, we expect the predicate to generate such lists in these cases!

Watch your wording! Very often, when you are able to express the task declaratively, an elegant and general Prolog solution will be straight-forward and often follows quite naturally from the task description.

Describing solutions

First, let us focus on what holds. There is no need to express what doesn't hold, because the predicate will not succeed anyways in such cases.

What do we want to describe?

Essentially, we want to describe lists of the form [...,a,b,c,...].

There are already some answers, with various drawbacks.

A pure way to do it uses the meta-predicate if_/3 from Indexing dif/2:

abc([X,Y,Z|Vs]) :-
        if_((X=a,Y=b,Z=c), true, abc([Y,Z|Vs])).

Generality

This works in all directions. First, let us try the most general query, where the single argument is a fresh variable:

?- abc(Vs).
Vs = [a, b, c|_5032] ;
Vs = [a, b, a, b, c|_5144] ;
Vs = [a, b, a, b, a, b, c|_5286] .

Thus, we can generate solutions, which is a very nice property of a relation!

The predicate is monotonic, and therefore iterative deepening is possible to fairly enumerate answers:

?- length(Vs, _), abc(Vs).
Vs = [a, b, c] ;
Vs = [a, b, c, _11600] ;
Vs = [a, a, b, c] ;
Vs = [_11982, a, b, c],
dif(_11982, a) ;
Vs = [a, b, c, _11600, _11606] .

From this, it follows that there are no solutions with less than 3 elements. In this case, that's quite obvious. In other cases, such results may be much less obvious from the task description.

Efficiency

The predicate is deterministic if its argument is sufficiently instantiated.

For example:

?- abc([a,b,c]).
true.

?- abc([z,a,b,c]).
true.

?- abc([a,b,c,z]).
true.

Note that no choice points remain in these cases!

Answer 4

Here are three approaches you could take, in roughly ascending order by flexibility:

First, is to use the predicate nth0/3 to find the position of a, b, and c in the list, and then check that the position of a < position of b < position of c. For multiple instances of a, b, and c in the list (e.g. [c,b,a,b,c,a]) nth0 will find positions of each matching element in turn, such that if there are three positions that fit the criteria (even if they are not the first positions) the predicate will succeed.

Hint 1.1: The syntax for nth0 to find the position of a.

nth0(PositionA,[c,b,a,b,c,a],a)

Hint 1.2: The syntax of less than (for completeness)

PositionA < PositionB

Partial Solution 1: A sequence of commands using nth0 to check that a, b, and c appear in some order in the list [c,b,a,b,c,a] (assembling the predicate is left to you)

nth0(PositionA,[c,b,a,b,c,a],a),
nth0(PositionB,[c,b,a,b,c,a],b),
nth0(PositionC,[c,b,a,b,c,a],c),
PositionA < PositionB,
PositionB < PositionC.

Second approach uses list pattern matching - we observe that, when going down the list, we must encounter a, then b, then c. To do that, we can construct three predicates that find a, b, and c, and then pass on the rest of the list where appropriate. We must construct these predicates to ignore other elements until they see their target.

Hint 2.1: The head of a predicate where a is the first element of the list

find_a([a|Rest]) :-

Hint 2.2: The head of a predicate where anything is the first element of the list

find_a([_|Rest]) :-

Hint 2.3: When we find a, we start looking for b

find_a([a|Rest]) :-
    find_b(Rest).

Hint 2.4: When we don't find a, we keep looking for a

find_a([_|Rest]) :-
    find_a(Rest).

Hint 2.5: Order matters (kind-of)

If we place find_a([a|Rest]) first in the knowledge base then Prolog will always try to unify against it first, so we'll match the first a we find. If we place it second, this will still work, but with a lot of extra backtracking, and we'll find each a in reverse order.

Hint 2.6: Don't forget the base case!

Remember that, even though you don't need to do anything once you find c, you still need to create a fact stating that it is the head of the list: find_c([c|_]).

The third approach is essentially a generalised version of the second approach - instead of creating predicates to find a, b, and c, you create a predicate that finds a list of elements in order.

Hint 3.1: Your predicate should take two lists and compare the heads of each

compare([A|Targets],[B|Checks]) :-

Hint 3.2: If the same variable name appears in multiple places, it must have the same value for the predicate to match

compare([A|Targets],[A|Checks]) :- % succeeds when the same element is at the head of each list

Hint 3.3: If they match, keep going down both lists

compare(Targets,Checks).

Hint 3.4: If they don't match, only go down the Checks list

compare([A|Targets],Checks).

Hint 3.5: Never forget the base case (when there are no more targets)

compare([],_).

Hint 3.6: As before, ordering is still important

compare([A|Targets],[A|Checks]) :- ... should be in the knowledge base before compare(Targets,[_|Checks]) :- ...

Solution 3:

compare([],_).
compare([A|Targets],[A|Checks]) :-
    compare(Targets,Checks).
compare(Targets,[_|Checks]) :-
    compare(Targets,Checks).

Hope this helps!