Je pense que vous avez l'idée que l'interprète Prolog traite des listes de différence comme quelque chose de spécial. Ce n'est pas le cas: Prolog n'est pas au courant du concept d'une liste de différence (ni de presque tous les concepts sauf certains sucre syntactique). Il ne voit que:
L=-(|(a, |(b, |(c, |(d, |(e, []))))), |(d, |(e, [])))
où -/2 et |/2 sont foncteurs et a, b, c, d, e et [] sont des constantes.
listes de différence sont tout simplement une technique de programmation (comme par exemple programmation dynamique est une technique aussi bien, le compilateur ne peut détecter ni traiter différemment les programmes de programmation dynamique). Il est utilisé pour unifier efficacement une partie (partiellement) non unifiée au plus profond d'une expression.
que vous voulez append/3 deux listes. Vous pouvez le faire comme suit:
%append(A,B,C).
append([],L,L).
append([H|T],L,[H|B]) :-
append(T,L,B).
Mais cela va dans O (n): vous devez d'abord parcourir la liste complète en premier. Si cette liste contient des milliers d'éléments, cela prendra beaucoup de temps.
Maintenant, vous pouvez définir vous un contrat que vous nourrir un append_diff/3 non seulement la liste, mais un tuple -(List,Tail) où List est une référence au début de la liste, et Tail est une référence à la fin de la liste non unifiée. Des exemples de structures qui satisfont à cette exigence sont Tail-Tail, [a|Tail]-Tail, [1,4,2,5|Tail]-Tail.
Maintenant, vous pouvez effectivement append_diff/3 à O (1) avec:
append_diff(H1-T1,T1-T2,H1-T2).
Pourquoi? Parce que vous unifier la queue non unifiée de la première liste avec la deuxième liste. Maintenant, la queue non unifiée des deuxièmes listes devient la queue de la liste finale.Alors, prenez par exemple:
append_diff([a|T1]-T1,[1,4,2,5|T2]-T2,L).
Si vous appelez le prédicat, comme vous le voyez ci-dessus, T1 unifierons avec [1,4,2,5|T2], maintenant la première liste se réduit à [a|[1,4,2,5|T2]] ou moins [a,1,4,2,5|T2], puisque nous avons aussi une référence à T2, nous pouvons "retourner" (dans Prolog rien n'est retourné), [a,1,4,2,5|T2]-T2: une nouvelle liste de différence avec une queue ouverte T2. Mais cela est seulement parce que vous donnez - vous-même signification particulière: pour Prolog - est tout simplement -, ce n'est pas moins , il ne calcule pas une différence, etc. Prolog ne pas attacher la sémantique à foncteurs. Si vous aviez utilisé + au lieu de -, cela n'aurait pas fait la moindre différence. Donc, pour revenir à votre question: vous dites simplement à Prolog que L = -([a,b,c,d,e],[d,e]) et plus tard, vous dites L = [a,b,c]. Maintenant, il est clair que ces deux expressions ne peuvent pas être unifiées. Donc, Prolog dit false.
La clé pour lire cette section est le mot * représente *. Si vous regardez dans le livre, quand les exemples peuvent être utilisés avec le niveau supérieur, l'interpréteur AKA, ils sont préfixés avec '? -'. Dans cette section, on lit 'Ainsi, la liste [a, b, c] peut être représentée, par exemple, par [a, b, c] - [] ou [a, b, c, d, e] - [d, e] ou [a, b, c, d, e | T] - [d, e | T] ou [a, b, c | T] -T où T est une liste. »Ce n'est donc pas un exemple courir avec le niveau supérieur, mais des exemples qui * représentent * ce que vous devriez penser, donc l'erreur lors de l'utilisation comme entrée dans le niveau supérieur. –
'L' ne peut pas être' '[a, b, c | [d, e]] - [d, e]' et '[a, b, c]'. Ce sont deux structures différentes. – lurker
@lurker Je vois cela maintenant, mais comme précisé dans les commentaires c'est probablement pourquoi je ne vois pas l'avantage pratique de la liste de différence. Vous aurez toujours besoin de l'étape * finalize * comme suggéré par Willem Van Onsem si vous voulez utiliser la liste concaténée. –