Reputation: 11
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).
Upvotes: 1
Views: 1802
Reputation: 24996
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.
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.
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 .
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.
See the answer by mat
Upvotes: 1
Reputation: 10152
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.
Upvotes: 2
Reputation: 40778
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.
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])).
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.
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!
Upvotes: 4
Reputation: 765
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 beforecompare(Targets,[_|Checks]) :- ...
Solution 3:
compare([],_).
compare([A|Targets],[A|Checks]) :-
compare(Targets,Checks).
compare(Targets,[_|Checks]) :-
compare(Targets,Checks).
Hope this helps!
Upvotes: 2