Geek Answers Handbook

Understanding Difference Lists (Prolog)

I am having trouble understanding a different list, especially in this predicate:

palindrome(A, A).
palindrome([_|A], A).
palindrome([C|A], D) :-
   palindrome(A, B),
   B=[C|D].

Can someone help me keep track of what is happening?

+4
source share
2 answers
palindrome(A, A).
palindrome([_|A], A).
palindrome([C|A], D) :-
   palindrome(A, B),
   B=[C|D].

Seeing the arguments of this predicate as a list of differences, the first sentence says that the list from Ato A(i.e. the empty list) is a palindrome.

The second section says that a singleton list is a palindrome, regardless of what that element is.

Do not panic! Dividing lists are simply lists with an explicit end pointer.

, [1,2,3], ; , []. [1,2,3] palindrome( [1,2,3], []) — , , [1,2,3] - [] .

, (, ) " ", : A - Z A = [1,2,3|Z] Z = []. , [1,2,3|[]] [1,2,3]. Z , A - - " " Z - ( , , ).

Z , , Z = [4|W], A - W, A = [1,2,3,4|W]. A - Z = [1,2,3,4|W] - [4|W], .. [1,2,3] [1,2,3,4 ...]. , . W = [5] - (.. A - Z, A - W...), A , .

- . / , , . .

. , [C|A]-D A-B , B [C|D]. A, D, B , C . ; V. , Z Y D B, "" :

palindrome([V|A], Z):- palindrome(A, Y), Y=[V|Z].

V ................. V ----
  ^                 ^ ^
  |                 | |
  |                 | Z
  A                 Y = [V|Z]

, ​​ ...... , V .

+7

, , , , .

-, , Prolog, , , , . , :

% List is a palindrome if List - [] is a palindrome:
palindrome( List ) :- palindrome(List, []).

( , List - Front Back, Front List Back, Front (List - Back).)

palindrome/2, " ", :

% The empty list (L-L) is a palindrome:
palindrome(L, L).

% A singleton list, ([X|L] - L), is a palindrome:
palindrome([X|L], L).

.

, : E... E

... (, ) .

, , : E... E Tail

[E | Rest], , ([E | Rest] - Tail) , (Rest - [E | Tail]) , /2:

palindrome( [E|Xs], Tail ) :- palindrome(Xs, [E|Tail]).

, .

! , , :

?- palindrome( X ).
X = [] ;
X = [_G1247] ;
X = [_G1247, _G1247] ;
X = [_G1247, _G1253, _G1247] ;
X = [_G1247, _G1253, _G1253, _G1247] 
....
0

More articles:


All Articles