9

  1. Can I get a recursive Prolog predicate having two arguments, called reverse, which returns the inverse of a list:

    Sample query and expected result:

    ?- reverse([a,b,c], L).
L = [c,b,a].

  2. A recursive Prolog predicate of two arguments called palindrome which returns true if the given list is palindrome.

    Sample query with expected result:

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

?- palindrome([b,a,c,a,b]).
true.
repeat
  • 18,496
  • 4
  • 54
  • 166
sam
  • 91
  • 1
  • 2

4 Answers4

7

Ad 1: It is impossible to define reverse/2 as a (directly edit thx to @repeat: tail) recursive predicate - unless you permit an auxiliary predicate.

Ad 2:

palindrome(X) :- reverse(X,X).

But the easiest way is to define such predicates with DCGs:

iseq([]) --> [].
iseq([E|Es]) --> iseq(Es), [E].

reverse(Xs, Ys) :-
   phrase(iseq(Xs), Ys).

palindrome(Xs) :-
   phrase(palindrome, Xs).

palindrome --> [].
palindrome --> [E].
palindrome --> [E], palindrome, [E].
false
  • 10,264
  • 13
  • 101
  • 209
7

There isn't an efficient way to define reverse/2 with a single recursive definition without using some auxiliary predicate. However, if this is nevertheless permitted, a simple solution which doesn't rely on any built-ins like append/3 (and should be applicable for most Prolog implementations) would be to use an accumulator list, as follows:

rev([],[]).
rev([X|Xs], R) :-
    rev_acc(Xs, [X], R).

rev_acc([], R, R).
rev_acc([X|Xs], Acc, R) :-
    rev_acc(Xs, [X|Acc], R).

rev/2 is the reversal predicate which simply 'delegates' to (or, wraps) the accumulator-based version called rev-acc/2, which recursively adds elements of the input list into an accumulator in reverse order.

Running this:

?- rev([1,3,2,x,4],L).
L = [4, x, 2, 3, 1].

And indeed as @false has already pointed out (+1),

palindrome(X) :- rev(X,X).
4

Just for curiosity here goes a recursive implementation of reverse/2 that does not use auxiliary predicates and still reverses the list. You might consider it cheating as it uses reverse/2 using lists and the structure -/2 as arguments.

reverse([], []):-!.
reverse([], R-R).
reverse(R-[], R):-!.
reverse(R-NR, R-NR).
reverse([Head|Tail], Reversed):-
  reverse(Tail, R-[Head|NR]),
  reverse(R-NR, Reversed).
gusbro
  • 22,357
  • 35
  • 46
  • 1
    Nice try, but incorrect. I gave you +1 anyway. `reverse(1-[], Ys).` should fail, but it succeeds with `Ys = 1.` Then, `reverse(Xs, Ys), Xs = [1].` should succeed but fails. So you are not cheating, but simply implementing another procedure. We agree not to call this a predicate - I presume. – false Jun 23 '11 at 20:25
  • 2
    @false. You're right!. This will only work with proper input lists. – gusbro Jun 24 '11 at 14:31
  • 1
    `reverse(Xs, [1]).` Isn't that a proper input list? It succeeds with `Xs = [1]-[].` – false Jun 24 '11 at 14:49
  • 2
    Ok, you beat me ;) It works only one-way, assuming the first argument is a proper list and the second argument is either another list or an uninstantiated variable. Will remove the answer in some minutes ;) – gusbro Jun 24 '11 at 15:07
  • 2
    Leave your answer! People often believe that similar things might work. – false Jun 24 '11 at 15:11
0
conca([],L,L).
conca([X|L1],L2,[X|L3]):- conca(L1,L2,L3).
rev([],[]).
rev([X|Y],N):- rev(Y,N1),conca(N1,[X],N).
palindrome([X|Y]):- rev([X|Y],N),equal([X|Y],N).
equal([X],[X]).
equal([X|Y],[X|Z]):- equal(Y,Z).
Kumar gaurav
  • 1
  • 1
    -1. No lines between your badly-named predicates, `conca/3` is just a copy of `append/3` which is ISO, `palindrome/1` destructures the list for no gain whatsoever (except preventing empty lists from being palindromes for no reason), and `equal/2` is no improvement on `=/2` except that it is unnecessarily more limiting. "What's new isn't good and what's good isn't new." – Daniel Lyons Jan 17 '17 at 22:42