List of exercises in the prologue
So my professor on campus asked us to solve this exercise, but it is very difficult and I have been trying for 2 days now. Anyway, these are:
I am given a list, for example [a,b,c,d,w,n,i,c,k,a,b,c,d,w]
, and in that list I need to find out if there is a suspicious sublist. A count is considered "suspicious" if
1) the same sublist is at the beginning and at the end,
2) contains "w",
3) its length is 5.
The list I am giving has a "suspicious" sublist.
If there is a suspicious sublist, the program should return the sublist, or if the program should not [o,k]
.
Any ideas would be appreciated, thanks! (sorry if I wrote something wrong)
EDIT
So, after some help, here's the asnwer:
checkMessage1(L,SL):-
suspiciousMessage1(L,SL).
checkMessage1(L,[o,k]):-
not(suspiciousMessage1(L,SL)).
suspiciousMessage1(L,SL):-
append(SL,Last,L),
append(_,SL,Last),
length(SL,5),
member(w,SL).
source to share
Prolog is a declarative language: describe a solution in terms of constraints and let the engine do the job.
We can determine the membership in the list like this:
contains( [X|Xs] , X ) :- ! .
contains( [_|Xs] , X ) :- contains(Xs,X) .
We can determine if the first element of a list is the same as its last element using the built-in predicate append/3
:
list_starts_and_ends_with_identical( [X|Xs] ) :-
append( [X|_] , [X] , [X|Xs] )
.
Or, if you prefer to use your own:
list_starts_and_ends_with_identical( [A|Xs] ) :-
list_ends_with( Xs , A )
.
list_ends_with( [A] , A ) .
list_ends_with( [B,C|D] , A ) :-
list_ends_with( [C|D] , A )
.
And we can list the sublists of the required length as follows:
sublist_of_length( Xs, L , Ys ) :- % to enumerate sublists of the desired length,
integer(L) , % - validate that the length is an integer, and
L > 0 , % - validate that the length is positive, and
length(Ys,L) , % - construct a list of unbound variables of the desired length, and
sl(Ys,L) % - invoke the helper
. %
sl( [X|Xs] , L ) :- % to enumerate sublists,
append( L , _ , [X|Xs] ) % - simply get the prefix of the desired length
. %
sl( [_|Xs] , L ) :- % on backtracking,
sl( Xs , L ) % - just recurse down on the tail of the list, discarding the first element.
.
Then all we have to do is collect the parts:
suspect_sublist( Xs , L ) :- % the source list Xs contains a suspect sublist L, IF...
sublist_of_length( Xs , 5 , L ) , % - L is a sublist of Xs having length 5, and
contains( L , w ) , % - L contains the atom 'w', and
list_starts_and_ends_with_identical( L ) , % - the first element of L is identical to the last.
. % Easy!
source to share
This is a good example of using DCG:
list_suspect(Xs, Ys) :-
length(Ys, 5),
phrase(( seq(Ys), ..., seq(Ys) ), Xs),
phrase((...,"w",...), Ys).
... --> [] | [_], ... .
seq([]) --> [].
seq([E|Es]) --> [E], seq(Es).
And here is a version using append/3
instead:
list_suspect(Xs, Ys) :-
Ys = [_,_,_,_,_],
append(Ys,Is, Xs),
append(_, Ys, Is).
append("w", _, W), % or: "w" = [C], W = [C|_]
append(_, W, Ys).
Is this more readable? I think no.
Part c [o,k]
looks a little unnatural to me, but it will:
list_ret(Xs, Ys) :-
list_suspect(Xs, Ys).
list_ret(Xs, Ys) :-
\+ list_suspect(Xs,_),
Ys = "ok".
source to share
one liner using append / 2
suspect(L, S) :-
length(S, 5), append([S,_,S], L), memberchk(w, S) -> true ; S = [o,k].
edit as specified false, buggy definition (lack of durability ?): rule changed
suspect(L, R) :-
length(S, 5), append([S,_,S], L), memberchk(w, S) -> S = R ; R = [o,k].
source to share