Deep Reverse dans PROLOG - Listes

Question

Hey j'essaye de créer un prédicat pour la génération d'un reverse profond sur les Listes imbriquées dans PROLOG.

Actuellement, je suis arrivé ce prédicat

reverse(L,A) :- rev(L,[], A). 
rev([],A,A). 
rev([H|L],R,A) :- rev(L,[H|R],A). 

Le résultat ressemble à ceci:

reverse([1,2,3],A). 
A = [3, 2, 1]. 

reverse([[0,1],2,3],A). 
A = [3, 2, [0, 1]]. 

Le problème est que la liste intérieure n'est pas inversée. Cela devrait ressembler à ceci:

reverse([[0,1],2,3],A). 
A = [3, 2, [1, 0]]. 

reverse([1,2,[3,4,5,[6,7],8],[9,10],11,12],A). 
A = [12,11,[10,9],[8,[7,6],5,4,3],2,1]. 

Merci pour toute aide.

Answer 1

Pour que les choses restent aussi simples que possible, nous pourrions ajouter un test si l'élément en cours de vérification est une liste ou non. S'il s'agit bien d'une liste, alors ses éléments devraient également être inversés. Ainsi, dans le code:

my_reverse(L,R) :- rev(L,[],R). 

rev([],A,A). 
rev([H|T],A,R) :- 
    (is_list(H) ->  % If H is a list 
     rev(H,[],X),   % then reverse H as well 
     rev(T,[X|A],R) 
    ; 
     rev(T,[H|A],R) 
    ). 

En outre, pas que cela importe vraiment, juste pour essayer d'éviter la confusion, notez comment je A et R pour respectivement Accumulator et Result. Dans votre code, ils sont actuellement échangés, ce qui - pour moi personnellement - peut être un peu déroutant, surtout quand les prédicats deviennent plus longs et plus complexes.

Quoi qu'il en soit, regardons les requêtes que vous avez fournies:

?- my_reverse([[0,1],2,3],R). 
R = [3, 2, [1, 0]]. 

?- my_reverse([1,2,[3,4,5,[6,7],8],[9,10],11,12],R). 
R = [12, 11, [10, 9], [8, [7, 6], 5, 4, 3], 2, 1]. 

Et quelques questions d'ordre général:

?- my_reverse(L,R). 
L = R, R = [] ; 
L = R, R = [_G2437] ; 
L = [_G2437, _G2443], 
R = [_G2443, _G2437] ; 
L = [_G2437, _G2443, _G2449], 
R = [_G2449, _G2443, _G2437] ; 
L = [_G2437, _G2443, _G2449, _G2455], 
R = [_G2455, _G2449, _G2443, _G2437] 
... 

?- my_reverse([[X,Y]|T],R), member(a,T), length(X,2). 
X = [_G2588, _G2591], 
T = [a], 
R = [a, [Y, [_G2588, _G2591]]] 
; 
X = [_G2594, _G2597], 
T = [a, _G2588], 
R = [_G2588, a, [Y, [_G2594, _G2597]]] 
; 
X = [_G2594, _G2597], 
T = [_G2582, a], 
R = [a, _G2582, [Y, [_G2594, _G2597]]] 
... 

Notez cependant que l'utilisation de ce prédicat, aucune terminaison se produit après avoir trouvé la première réponse à la requête:

?- my_reverse(X,[X]). 
X = [X] ; 
... 

Mais puisque ce n'était pas une exigence/demande La question de OP, j'ai supposé que c'était correct.

EDIT:

S'il vous plaît lire @mat's answer comme suite à ce problème.

Answer 2

La façon dont vous représentez vos données est appelée defaulty, parce que vous avez besoin d'un défaut cas en raisonnant dessus:

• est-il une liste? &flèche droite; quelque chose tient
• sinon & rightarrow; quelque chose d'autre tient.

Une telle représentation est une riche source de problèmes. Considérons par exemple my_reverse/2 de l'autre réponse.Le principal problème avec c'est que prématurément et mal   engage à l'un des cas, bien que les deux cas sont encore possibles:

 
?- my_reverse([X], Ls). 
Ls = [X]. 

Mais cette réponse ne vaut que pour le cas où X est pas une liste! Ce problème conduit à l'étrange comportement suivant du prédicat:

 
?- my_reverse([X], Ls), X = [1,2,3]. 
Ls = [[1, 2, 3]], 
X = [1, 2, 3]. 

Cela signifie que même si X est une liste, ses éléments sont pas inversés!

Vous devriez toujours viser des représentations plus propres pour distinguer les cas qui peuvent survenir.

Par exemple, que diriez-vous de la façon suivante pour représenter vos données:

• list(Ls) représente la listeLs
• n(N) représente le nombre N.

Avec une telle représentation, nous pouvons distinguer symboliquement les cas. Je laisse cela comme point de départ pour une solution plus déclarative.