Palindrome (homework)
I tried to write a Prolog program using lists. However, I have to use lists of differences and the output should be:
The i th item of the list is the same as the (ni + 1) th item of the list, and n is the length of the list. For example, [a,X,c,b,Y]
should give X = b
and Y = a
. I couldn't find a similar palindrome example in other questions.
So far I have implemented:
% length of the list
len([], 0).
len([H|T], B) :-
len(T, NT),
B is NT + 1.
% return the ith element of the list
match([H|_], 0, H) :-
!.
match([_|T], N, H) :-
N > 0,
N1 is N-1,
match(T, N1, H).
However, I was unable to finish. Please help me!
source to share
Use specific grammar sentences!
DCG, Prolog's core function, makes Difference Lists easy to use, allowing you to write concise and efficient code with minimal effort!
Want to know more? Just follow the points:
- DCG has its own tag on StackOverflow, dcg .
-
en.wikipedia.org has an extensive article on DCG .
Without any further errors, go into the code:
palindrome -> []. palindrome -> [_]. palindrome -> [X], palindrome, [X]. % Alternatively , we could also use the following more compact definition: palindrome -> [] | [_] | [X], palindrome, [X].
Done. Let's run some queries! First, the OP's request gave:
?- phrase(palindrome, [a,X,c,b,Y]).
X = b, Y = a
; false.
In German, "corn" is called "mais" . If we put "siam" (the old name for "Kingdom of Thailand") in front, we get a delicious palindrome:
? - set_prolog_flag (double_quotes, chars). true. ? - phrase (palindrome, "sia mm ais"). true ; false. ? - phrase (palindrome, "of sia m ais"). % or kick one middle ' m ' character true% ... for an odd-length palindrome ; false.
Finally, don't forget about the most general query:
?- phrase(palindrome, Xs).
Xs = []
; Xs = [_A]
; Xs = [_A,_A]
; Xs = [_A,_B,_A]
; Xs = [_A,_B,_B,_A]
; Xs = [_A,_B,_C,_B,_A]
...
At prolog-toplevel, we can use the built-in Prolog predicate listing/1
to look into the code the DCG has been "translated" into - at this level internal usedifference-lists:
?- listing(palindrome//0).
palindrome(A, A).
palindrome([_|A], A).
palindrome([C|A], D) :-
palindrome(A, B),
B = [C|D].
true.
source to share