L'inversion d'une Liste en Prolog
J'ai fini un devoir à la maison pour ma programmation de classe. J'étais censé créer un programme Prolog qui inverse une liste. Toutefois, je vais avoir du mal à comprendre pourquoi il fonctionne exactement.
%1. reverse a list
%[a,b,c]->[c,b,a]
%reverse(list, rev_List).
reverse([],[]). %reverse of empty is empty - base case
reverse([H|T], RevList):-
reverse(T, RevT), conc(RevT, [H], RevList). %concatenation
Qu'est-ce exactement RevT dans ce cas? Je sais que c'est censé représenter l'inverse de T ou le reste de la liste, mais je ne vois pas comment il pourrait avoir une valeur que je n'ai pas attribué à quoi que ce soit. Est-il juste de servir le même but que RevList mais pour chaque appel récursif?
Aussi, pourquoi dois-je utiliser [H] au lieu de simplement H dans mon conc() appel de fonction? Ne pas H se référer à la tête de la liste (ex: [H])? Ou faut-il tout simplement se référer à l'élément en tête de liste (juste en H)?
S'il vous plaît aider éclaircir ce point pour moi. J'ai du mal à comprendre la logique derrière ce type de programmation.
J'ai également commencé à mettre en place mon propre arrière/2 avec Prologue 🙂
OriginalL'auteur Jared | 2013-10-19
Vous devez vous connecter pour publier un commentaire.
Votre solution expliqué:
Si nous inversons la liste vide, on obtient la liste vide.
Si nous inversons la liste [H|T] , nous nous retrouvons avec la liste obtenue par inversion de T et la concaténation avec [H] .
De voir que la clause récursive est correct, examiner la liste [a,b,c,d] . Si nous inversons la queue de cette liste, nous obtenons [d,c,b] . La concaténation de ce avec [un] produit [d,c,b,a] , qui est l'inverse de [a,b,c,d]
Une autre solution inverse:
appel:
Pour de plus amples informations, veuillez consulter: http://www.learnprolognow.org/lpnpage.php?pagetype=html&pageid=iaa-htmlse25
Z est le résultat final.
OriginalL'auteur Cornel Marian
Prolog listes sont de simples structures de données:
./2
[]
.[a]
, est en fait cette structure:.(a,[])
.[a,b]
est en fait cette structure:.(a,.(b,[]))
[a,b,c]
est en fait cette structure:.(a,.(b,.(c,[])))
La notation crochets est sucre syntaxique pour vous épargner de passer votre vie en vous tapant des parenthèses. Ne pas oublier qu'il est plus facile sur les yeux.
À partir de cela, nous obtenons la notion de tête de la liste (le système de référence dans le ultrapériphériques
./2
structure) et de la queue de la liste (avec la sous-liste contenue dans cette ultrapériphériques./2
structure de données.C'est essentiellement la même structure de données que vous consultez pour un classique de liste liée individuellement dans C:
où la
next
pointeur est NULL ou une autre structure de liste.Donc, de ce, nous obtenons le simple [naïf] la mise en œuvre de l'arrière/2:
Ce même algorithme de travail de l'inversion d'une liste liée individuellement de manière plus classique en langage de programmation.
Cependant, cet algorithme n'est pas très efficace: il présente O(n2) le comportement, pour commencer. Il n'est également pas la queue récursive, ce qui signifie qu'une liste de longueur suffisante, va provoquer un débordement de pile.
Il convient de noter qu'afin d'ajouter un élément à un prologue de la liste exige traversant l'ensemble de la liste, ajoutant est une opération triviale, en raison de la structure d'un prologue de la liste. Nous pouvons ajouter un élément à une liste existante comme simplement comme:
Un idiome commun en prolog est d'utiliser un travailleur prédicat avec un accumulateur. Cela rend le
reverse/2
mise en œuvre beaucoup plus efficace et (peut-être) un peu plus facile à comprendre. Ici, nous avons inversé la liste par semis notre accumulateur, comme une liste vide. On itère sur la liste source. Comme nous nous rencontrons élément dans la liste source de nous ajouter à la liste inversée, produisant ainsi l'inversion de liste que nous allons.Maintenant, vous avez un
reverse/2
de mise en œuvre qui s'exécute en O(n) fois. C'est aussi la queue récursive, ce qui signifie qu'il peut gérer une liste de n'importe quelle longueur sans souffler sa pile.OriginalL'auteur Nicholas Carey
Envisager l'utilisation d'un DCG au lieu de cela, ce qui est beaucoup plus facile à comprendre:
Exemple:
Voir le DCG balise description pour plus d'informations, et la dcg la balise pour les questions et les réponses!
"Envisager l'utilisation d'un DCG au lieu de cela, ce qui est beaucoup plus facile à comprendre" --- le DCG est difficile à comprendre sans utiliser de prétendre le contraire .
fonctionne très bien avec
reverse([a,b,c],Q]
mais! non-résiliation avecreverse(P,[a,b,c])
OriginalL'auteur mat
Variables Prolog sont des "espaces réservés" pour les relations avec les arguments. Ce que nous savons, après un appel réussi, c'est exactement ce que les arguments spécifiés tenir pour que relation.
Puis
RevT
aura une valeur, si l'appel à réussir. Plus précisément, c'est le dernier argument de l'appelconc(RevT, [H], RevList)
, quand la liste est pas vide. Sinon, ce sera la liste vide.Oui, H désigne la première élément (généralement appelé élément) de la liste, alors nous devons "remodeler" pour être une liste (de seulement 1 élément), tel que requis par la conc/3, c'est une autre relation entre listes.
OriginalL'auteur CapelliC
Juste une remarque sur tests
reverse/2
prédicat définitions, trop long pour un commentaire.L'inversion d'une liste est l'exemple "hello world" pour l'introduction de QuickCheck, ce qui signifie que vous pouvez utiliser pour aider à tester votre définition. Tout d'abord, nous définissons un propriété qui détient pour le compte de
reverse/2
prédicat: l'inversion d'une liste à deux reprises, doit donner la liste originale, que nous pouvons traduire:À l'aide de Logtalk de
lgtunit
outil QuickCheck mise en œuvre:Ou tout simplement:
Mais nous avons besoin d'une définition de propriété de tester avec le deuxième argument lié:
Nous pouvons maintenant faire:
Mais notez que cette propriété-base/test aléatoire ne pas vérifier la non-terminaison cas, car ceux-ci ne se produire lorsque les retours en arrière après la première solution.
OriginalL'auteur Paulo Moura
Suivant est le cas typique de la mise en œuvre de l'arrière/2 .
Il n'est toutefois le problème comme il est marqué à soufflet avec des "non-résiliation" .
.
OriginalL'auteur Kintalken
'arrière/2' .
/*
Ce qui suit est une mise en œuvre de l'arrière/2
que je viens d'inventer qui ne souffre pas
à partir d'un non-résiliation problème pour
reverse(P,[])
.*/
"mise en œuvre".
"testing".
'des tests : partie 1".
'des tests : part 2".
'des tests : la partie 3' .
OriginalL'auteur Kintalken