Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Recursive Prolog predicate for reverse / palindrome

  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.
    
like image 636
sam Avatar asked Jun 22 '11 15:06

sam


2 Answers

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).
like image 61
gusbro Avatar answered Oct 14 '22 20:10

gusbro


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].
like image 41
false Avatar answered Oct 14 '22 20:10

false