list - リバース/パリンドロームの再帰的プロローグ述語

Question

1. リストの逆を返すreverseと呼ばれる2つの引数を持つ再帰的なProlog述語を取得できますか？

   サンプルクエリと期待される結果：

   ？-reverse（[a、b、c]、L）。
   L = [c、b、a]。
   

2. 呼び出された2つの引数の再帰的Prolog述語はpalindrome、指定されたリストが回文である場合にtrueを返します。

   期待される結果を含むサンプルクエリ：

   ？-回文（[a、b、c]）。
   false。
   
   ？-回文（[b、a、c、a、b]）。
   本当。
   

Answer 1

広告1：reverse/2（ thxを@repeat：tailに直接編集する）再帰述語として定義することは不可能です-補助述語を許可しない限り。

広告2：

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

しかし、最も簡単な方法は、DCGを使用してそのような述語を定義することです。

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].

Answer 2

reverse/2補助述語を使用せずに単一の再帰的定義で定義する効率的な方法はありません。ただし、それにもかかわらずこれが許可されている場合、次のような組み込み関数に依存しないappend/3(そしてほとんどの Prolog 実装に適用できるはずである)簡単な解決策は、次のようにaccumulator listを使用することです。

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/2rev-acc/2は、入力リストの要素をアキュムレータに逆の順序で再帰的に追加する、と呼ばれるアキュムレータベースのバージョンに単純に「委譲」(またはラップ) する反転述語です。

これを実行する：

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

実際、@false が既に指摘しているように (+1)、

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

Answer 3

好奇心のために、reverse/2 の再帰的な実装を紹介します。これは、補助述語を使用せず、リストを反転します。リストと構造体 -/2 を引数として使用して reverse/2 を使用するため、不正行為と見なされる場合があります。

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).

Answer 4

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).