Veuillez me guider dans cet exemple récursif "Erlang Programming"

Question

A partir de la page 90 d'Erlang Programmation par Cesarini et Thomson, il y a un exemple qui n'a pas de discussion détaillée. Je suis tout à fait le novice de la programmation fonctionnelle et de la pensée récursive, donc je ne suis pas familier dans la résolution de problèmes de cette façon.

« Par exemple, la fonction suivante se confond deux listes (de la même longueur) en entrelaçant leurs valeurs: »

merge(Xs,Ys) -> lists:reverse(mergeL(Xs,Ys,[])). 

mergeL([X|Xs],Ys,Zs) -> mergeR(Xs,Ys,[X|Zs]); 
mergeL([],[],Zs) -> Zs. 

mergeR(Xs,[Y|Ys],Zs) -> mergeL(Xs,Ys,[Y|Zs]); 
mergeR([],[],Zs) -> Zs. 

Comment ça marche? Merci!

Answer 1

Cette fonction est appelée d'abord:

merge(Xs,Ys) -> lists:reverse(mergeL(Xs,Ys,[])). 

La liste vide [] passé à MERGEL est l'accumulateur - c'est là la réponse viendra. Notez que la première fonction appelle mergeL - la fusion à gauche.

Feignons que cette fonction est appelée comme si:

merge([1, 2, 3], [a, b, c]) 

Deux listes de la même longueur. Cette première fonction appelle ensuite mergeL:

mergeL([X|Xs],Ys,Zs) -> mergeR(Xs,Ys,[X|Zs]); 
mergeL([],[],Zs) -> Zs. 

Il existe 2 clauses dans la fusion à gauche. L'appel à mergeL avec les arguments correspondra à ces clauses dans l'ordre descendant.

La seconde de ces clauses a trois paramètres - les deux premiers sont des listes vides []. Cependant, la première fois que mergeL est appelée ces deux listes ne sont pas vides, ce sont les listes Xs et Ys qui correspondent à la première clause.

Permet de répartir les résultats. Ceci est l'appel à MERGEL:

MERGEL ([1, 2, 3], [a, b, c], [])

et elle correspond à la première clause de la façon suivante:

X = 1 
Xs = [2, 3] 
Ys = [a, b, c] 
Zs = [] 

Ceci est dû à la forme particulière de la liste:

[X | Xs] 

Cela signifie en jeu X à la tête de la liste (un élément individuel) et faire Xs la queue de la liste (une liste). Nous construisons ensuite le nouvel appel de fonction.

Nous pouvons ajouter la valeur X au début de la liste Z de la même façon que nous l'avons fait pour obtenir le premier appel mergeR:

mergeR ([2, 3], [a, b, c], [ 1])

L'argument final est une liste à un élément causée par l'ajout d'un élément en tête d'une liste vide.

Ceci se zippe jusqu'à la fin.

En fait, la clause finale de mergeL est redondante. Par définition, cette fonction sera épuisée dans la clause finale de mergeR (mais je laisserai cela comme un exercice pour le lecteur).

Answer 2

étape à travers elle

merge([1,2],[3,4]) 
reverse(mergeL([1,2],[3,4],[])) 
reverse(mergeR([2],[3,4],[1])) 
reverse(mergeL([2],[4],[3,1])) 
reverse(mergeR([], [4], [2,3,1])) 
reverse(mergeL([], [], [4,2,3,1])) 
reverse([4,2,3,1]) 
[1,3,2,4] 

Il est toujours bon de travailler ces fonctions à la main sur un morceau de papier avec une petite entrée où vous essayez de comprendre. Vous verrez rapidement comment cela fonctionne.

Answer 3

Ce que l'exemple fait est de définir quelques états que la récursivité va traverser. Il y a 3 'fonctions' qui sont définies: merge, mergeL et mergeR.

Les listes à fusionner sont X et Y, tandis que les Z sont le résultat de la fusion.

La fusion débutera par l'appel de 'fusionner' et la fourniture de deux listes. La première étape consiste à appeler mergeL avec les deux listes à fusionner et un ensemble de résultats vide. [X | Xs] prend le premier élément de la liste (très semblable à array_shift). Cet élément est ajouté à la tête du résultat ([X | Zs] le fait). Ce résultat (contenant un élément maintenant) est ensuite passé à l'appel suivant, mergeR. mergeR fait la même chose, seulement il prend un élément de la deuxième liste. Ce comportement continuera tant que les listes fournies à mergeL ou mergeR ne sont pas vides. Lorsque mergeL ou mergeR est appelé avec deux listes vides ([]) et un resultset (Zs), il renverra le resultset (et ne fera pas une autre exécution, arrêtant ainsi la récursion).

Résumé:

Le début de la récursion est la première ligne, qui définit la « fusion ». Ce début mettra tout en mouvement en appelant le premier mergeL.

Le corps de la récursivité est les lignes 2 et 4, qui définissent le comportement ou mergeL et mergeR, qui s'appellent l'un et l'autre.

L'arrêt de la récursivité est défini par les lignes 3 et 5, qui indiquent fondamentalement au tout ce qu'il faut faire lorsqu'il n'y a plus d'éléments dans le tableau.

Espérons que cela aide!

Answer 4

je cherche toujours les fonctions qui stoppent la récursion d'abord, dans ce cas:

mergeL([],[],Zs) -> Zs. 

et

mergeR([],[],Zs) -> Zs. 

deux personnes termineront essentiellement la « fusion » lorsque les deux premiers les paramètres sont des listes vides.

Alors je regarde le premier appel de la fonction:

merge(Xs,Ys) -> lists:reverse(mergeL(Xs,Ys,[])). 

Ignorer l'inverse pour une seconde, vous verrez que le dernier paramètre est une liste vide.Donc je m'attendrais à ce que les différentes fonctions mergeL et mergeR déplacent les éléments de ce tableau dans le paramètre final - et quand elles sont toutes déplacées, la fonction finira par se terminer (bien qu'appelant finalement la fonction inverse bien sûr)

Et ça est exactement ce que les autres fonctions font:

mergeL([X|Xs],Ys,Zs) -> mergeR(Xs,Ys,[X|Zs]); 

prend le premier élément de X et met dans le tableau Z et

mergeR(Xs,[Y|Ys],Zs) -> mergeL(Xs,Ys,[Y|Zs]); 

prend le premier élément de Y et il met dans le tableau Z . L'appel de la mergeR à partir de mergeL et vice versa fait la partie d'entrelacement. Ce qui est intéressant à voir (et facile à corriger) est que les tableaux X et Y doivent être de la même longueur ou vous finirez par appeler mergeL ou mergeR avec un tableau vide dans X ou Y - et cela a gagné ' t correspond soit à [X | Xs] ou [Y | Ys].

Et la raison de l'inverse est simplement autour de l'efficacité relative de [X | Zs] vs [Zs | X]. Le premier est beaucoup plus efficace.