Accumulateurs, conj et récursivité
https://stackoverflow.com//questions/10666228
-
11-12-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
J'ai résolu 45 problèmes sur 4clojure.com et j'ai remarqué un problème récurrent dans la façon dont j'essaie de résoudre certains problèmes en utilisant la récursivité et les accumulateurs.
Je vais essayer d'expliquer du mieux que je peux ce que je fais pour aboutir à des solutions floues en espérant que certains Clojurers "obtiendraient" ce que je n'obtiens pas.
Par exemple, le problème 34 demande d'écrire une fonction (sans utiliser gamme) prenant deux entiers comme arguments et crée une plage (sans utiliser de plage).En termes simples, vous faites (...1 7) et vous obtenez (1 2 3 4 5 6).
Or, cette question ne vise pas à résoudre ce problème particulier.
Et si je vouloir résoudre ce problème en utilisant la récursion et un accumulateur ?
Mon processus de réflexion est le suivant :
J'ai besoin d'écrire une fonction prenant deux arguments, je commence par (fn [x y] )
Je devrai récurer et garder une trace d'une liste, j'utiliserai un accumulateur, donc j'écris une 2ème fonction à l'intérieur de la première en prenant un argument supplémentaire :
(fn [xy
((fn g [xy acc] ...) x y '())
(apparemment, je ne peux pas formater correctement ce code Clojure sur SO !?)
Ici, je ne suis déjà pas sûr de le faire correctement :la première fonction doit prenez exactement deux arguments entiers (pas mon appel) et je ne suis pas sûr :si je souhaite utiliser un accumulateur, puis-je utiliser un accumulateur sans créer de fonction imbriquée ?
Alors je veux conj, mais je ne peux pas faire :
(conj 0 1)
donc je fais des choses bizarres pour être sûr d'avoir d'abord une séquence et je me retrouve avec ça :
(fn
[x y]
((fn g [x y acc] (if (= x y) y (conj (conj acc (g (inc x) y acc)) x)))
x
y
'()))
Mais alors cela produit ceci :
(1 (2 (3 4)))
Au lieu de cela:
(1 2 3 4)
Donc je finis par faire un supplément aplatir et ça marche mais c'est totalement moche.
Je commence à comprendre certaines choses et je commence même, dans certains cas, à "penser" de manière plus clojuresque mais j'ai du mal à écrire la solution.
Par exemple ici, j'ai décidé :
- utiliser un accumulateur
- récidiver en incrémentant X jusqu'à ce qu'il atteigne oui
Mais je me retrouve avec la monstruosité ci-dessus.
Il y a un parcelle moyen de résoudre ce problème et, encore une fois, ce n'est pas ce que je recherche.
Ce que je recherche, c'est comment, après avoir décidé de contre/conj, d'utiliser un accumulateur et de récurer, je peux me retrouver avec ceci (non écrit par moi) :
#(loop [i %1
acc nil]
(if (<= %2 i)
(reverse acc)
(recur (inc i) (cons i acc))))
Au lieu de cela:
((fn
f
[x y]
(flatten
((fn
g
[x y acc]
(if (= x y) acc (conj (conj acc (g (inc x) y acc)) x)))
x
y
'())))
1
4)
Je suppose que c'est un début pour pouvoir résoudre quelques problèmes mais je suis un peu déçu par les solutions moches que j'ai tendance à produire...
La solution
je pense qu'il y a quelques choses à apprendre ici.
d'abord, une sorte de règle générale - les fonctions récursives ont généralement un ordre naturel, et l'ajout d'un accumulateur inverse cela.vous pouvez le voir parce que quand un "normal" (sans accumulateur) la fonction récursive s'exécute, elle effectue un certain travail pour calculer une valeur, puis récidive pour générer la queue de la liste, se terminant finalement par une liste vide.en revanche, avec un accumulateur, vous commencez avec la liste vide et ajoutez des éléments au premier plan - elle s'agrandit dans l'autre sens.
donc généralement, lorsque vous ajoutez un accumulateur, vous obtenez un ordre inversé.
maintenant, souvent, cela n'a plus d'importance.par exemple, si vous générez non pas une séquence mais une valeur qui est l'application répétée d'un commutatif opérateur (comme l’addition ou la multiplication).alors vous obtenez la même réponse dans les deux cas.
mais dans votre cas, cela va avoir de l'importance.vous allez obtenir la liste à l'envers :
(defn my-range-0 [lo hi] ; normal recursive solution
(if (= lo hi)
nil
(cons lo (my-range-0 (inc lo) hi))))
(deftest test-my-range-1
(is (= '(0 1 2) (my-range-0 0 3))))
(defn my-range-1 ; with an accumulator
([lo hi] (my-range-1 lo hi nil))
([lo hi acc]
(if (= lo hi)
acc
(recur (inc lo) hi (cons lo acc)))))
(deftest test-my-range-1
(is (= '(2 1 0) (my-range-1 0 3)))) ; oops! backwards!
et souvent, le mieux que vous puissiez faire pour résoudre ce problème est simplement d'inverser cette liste à la fin.
mais il existe ici une alternative : nous pouvons en fait faire le travail à l'envers.au lieu de incrémentation la limite basse que vous pouvez décrémenter la limite haute :
(defn my-range-2
([lo hi] (my-range-2 lo hi nil))
([lo hi acc]
(if (= lo hi)
acc
(let [hi (dec hi)]
(recur lo hi (cons hi acc))))))
(deftest test-my-range-2
(is (= '(0 1 2) (my-range-2 0 3)))) ; back to the original order
[remarque - il existe une autre façon d'inverser les choses ci-dessous ;je n'ai pas très bien structuré mon argument]
deuxième, comme vous pouvez le voir dans my-range-1 et my-range-2, une bonne façon d'écrire une fonction avec un accumulateur est de la présenter comme une fonction avec deux ensembles d'arguments différents.cela vous donne une implémentation très propre (à mon humble avis) sans avoir besoin de fonctions imbriquées.
vous avez également des questions plus générales sur les séquences, conj etc.ici, clojure est un peu compliqué, mais aussi utile.ci-dessus, j'ai donné une vue très traditionnelle avec des listes basées sur les inconvénients.mais clojure vous encourage à utiliser d'autres séquences.et contrairement aux listes d'inconvénients, les vecteurs grandissent vers la droite et non vers la gauche.donc un autre Un moyen d'inverser ce résultat est d'utiliser un vecteur :
(defn my-range-3 ; this looks like my-range-1
([lo hi] (my-range-3 lo hi []))
([lo hi acc]
(if (= lo hi)
acc
(recur (inc lo) hi (conj acc lo)))))
(deftest test-my-range-3 ; except that it works right!
(is (= [0 1 2] (my-range-3 0 3))))
ici conj s'ajoute à droite.je n'ai pas utilisé conj dans my-range-1, donc le voici réécrit pour être plus clair :
(defn my-range-4 ; my-range-1 written using conj instead of cons
([lo hi] (my-range-4 lo hi nil))
([lo hi acc]
(if (= lo hi)
acc
(recur (inc lo) hi (conj acc lo)))))
(deftest test-my-range-4
(is (= '(2 1 0) (my-range-4 0 3))))
notez que ce code ressemble très semblable à my-range-3 mais le résultat est à l'envers car nous partons d'une liste vide, pas d'un vecteur vide.dans les deux cas, conj ajoute le nouvel élément dans la position "naturelle".pour un vecteur c'est à droite, mais pour une liste c'est à gauche.
et je viens de penser que vous ne comprenez peut-être pas vraiment ce qu'est une liste.fondamentalement un cons crée une boîte contenant deux choses (ses arguments).le premier est le contenu et le second est le reste de la liste.donc la liste (1 2 3) est fondamentalement (cons 1 (cons 2 (cons 3 nil))).en revanche, le vecteur [1 2 3] fonctionne plus comme un tableau (même si je pense qu'il est implémenté à l'aide d'un arbre).
donc conj est un peu déroutant car la façon dont cela fonctionne dépend du premier argument.pour une liste, ça appelle cons et ainsi ajoute des choses à gauche.mais pour un vecteur, il étend le tableau (chose semblable) vers la droite.notez également que conj prend une séquence existante comme premier argument et une chose à ajouter comme deuxième, tandis que cons est l'inverse (la chose à ajouter vient en premier).
tout le code ci-dessus disponible sur https://github.com/andrewcooke/clojure-lab
mise à jour:j'ai réécrit les tests pour que le résultat attendu soit une liste citée dans les cas où le code génère une liste. = comparera les listes et les vecteurs et retournera vrai si le contenu est le même, mais le rendre explicite montre plus clairement ce que vous obtenez réellement dans chaque cas.noter que '(0 1 2) avec un ' devant c'est comme (list 0 1 2) - le ' arrête l'évaluation de la liste (sans elle, 0 serait traité comme une commande).
Autres conseils
Après avoir lu tout cela, je ne sais toujours pas pourquoi vous auriez besoin d'un accumulateur.
((fn r [a b]
(if (<= a b)
(cons a (r (inc a) b))))
2 4)
=> (2 3 4)
semble être une solution récursive assez intuitive.la seule chose que je changerais dans le "vrai" code est d'utiliser lazy-seq afin que vous ne manquiez pas de pile pour de grandes plages.
comment je suis arrivé à cette solution:
Lorsque vous envisagez d'utiliser la récursivité, je trouve qu'il est utile d'essayer d'énoncer le problème avec le moins de termes possibles que vous puissiez imaginer, et d'essayer de confier autant de « travail » à la récursivité elle-même.
En particulier, si vous pensez pouvoir supprimer un ou plusieurs arguments/variables, c'est généralement la voie à suivre - du moins si vous voulez que le code soit facile à comprendre et à déboguer ;parfois, vous finissez par compromettre la simplicité en faveur de la vitesse d'exécution ou en réduisant l'utilisation de la mémoire.
Dans ce cas, ce que je pensais en commençant à écrire était :"le premier argument de la fonction est également l'élément de début de la plage et le dernier argument est le dernier élément".La pensée récursive est quelque chose pour lequel vous devez en quelque sorte vous entraîner, mais une solution assez évidente consiste alors à dire :un gamme [a, b] est une séquence commençant par l'élément a suivi de un gamme de [a + 1, b].Les plages peuvent donc effectivement être décrites de manière récursive.Le code que j'ai écrit est à peu près une implémentation directe de cette idée.
Addenda:
J'ai constaté que lors de l'écriture de code fonctionnel, il est préférable d'éviter les accumulateurs (et les index).Certains problèmes en nécessitent, mais si vous pouvez trouver un moyen de vous en débarrasser, vous ferez généralement mieux de le faire.
addenda 2 :
Concernant les fonctions récursives et les listes/séquences, le La façon la plus utile de réfléchir lors de l'écriture de ce type de code est d'énoncer votre problème en termes de "premier élément (tête) d'une liste" et "le reste de la liste (queue)".
Je ne peux pas ajouter aux réponses déjà bonnes que vous avez reçues, mais je vais répondre en général. Au fur et à mesure que vous suivez le processus d'apprentissage du clojure, vous pouvez constater que beaucoup de solutions mais toutes les solutions ne peuvent pas être résolues à l'aide de CLOJURE intégrées, comme carte et de penser à des problèmes en termes de séquences. Cela ne signifie pas que vous ne devez pas résoudre les choses récursives, mais vous entendrez - et je crois que ce sera des conseils sages - que Récupération de clojure est de résoudre des problèmes de niveau très bas que vous ne pouvez pas résoudre une autre manière.
J'arrive à faire beaucoup de traitement de fichier .csv et j'ai récemment reçu un commentaire que Nth crée des dépendances. Cela fait et l'utilisation des cartes peut me permettre d'obtenir des éléments de comparaison par nom et non.
Je ne vais pas jeter le code qui utilise Nth avec des données analysées de Clojure-CSV dans deux petites applications déjà en production. Mais je vais penser à des choses de manière plus séquence la prochaine fois.
Il est difficile d'apprendre des livres qui parlent de vecteurs et de nth, de la boucle .. recurent et ainsi de suite, puis réalisez que l'apprentissage de la clojure vous pousse vers l'avant.
Une des choses que j'ai trouvées, c'est bon pour apprendre le clojure, la communauté est respectueuse et utile. Après tout, ils aident quelqu'un dont la première langue d'apprentissage était Fortran IV sur un cyber CDC avec des cartes de poinçon et dont le premier langage de programmation commercial était PL / I.
Si je résolvais ce problème en utilisant un accumulateur, je ferais quelque chose comme :
user=> (defn my-range [lb up c]
(if (= lb up)
c
(recur (inc lb) up (conj c lb))))
#'user/my-range
puis appelle-le avec
#(my-range % %2 [])
Bien sûr, j'utiliserais letfn ou quelque chose à contourner sans avoir defn disponible.
Alors oui, vous avez besoin d'une fonction interne pour utiliser l'approche accumulateur.
Mon processus de pensée est qu'une fois que j'aurai terminé, la réponse que je veux retourner sera dans l'accumulateur.(Cela contraste avec votre solution, où vous faites beaucoup de travail pour trouver la condition finale.) Je cherche donc ma condition finale et si je l'ai atteinte, je rends l'accumulateur.Sinon, je colle l'élément suivant sur l'accumulateur et je récidive pour un boîtier plus petit.Il n'y a donc que 2 choses à comprendre, quelle est la condition finale et ce que je veux mettre dans l'accumulateur.
Utiliser un vecteur aide beaucoup car conj y sera ajouté et il n'est pas nécessaire d'utiliser reverse.
je suis aussi sous 4clojure, d'ailleurs.J'ai été occupé donc j'ai pris du retard ces derniers temps.
On dirait que votre question est plus sur "Comment apprendre" alors un problème technique / code. Vous finissez par écrire ce type de code car de quelque manière que ce soit de quelque manière que ce soit de quelque manière que ce soit, vous avez appris la programmation en général ou en clojure dans des informations spécifiques a créé une «autoroute neurale» dans votre cerveau qui vous fait penser aux solutions de cette manière particulière et vous finissez par écrire un code d'écriture. comme ça. Fondamentalement chaque fois que vous êtes confronté à un problème (dans cette affaire particulière de récursion et / ou d'accumulation), vous finissez par utiliser cette "autoroute neurale" et monte toujours avec ce type de code.
La solution pour vous débarrasser de cette "autoroute neurale" est d'arrêter de rédiger un code pour le moment, de garder ce clavier à l'écart et de commencer à lire beaucoup de code de clojure existant (des solutions existantes du problème de 4Clojure à des projets open source sur Github) Et pensez-y profondément (même lire une fonction 2 à 3 fois pour le laisser vraiment s'installer dans votre cerveau). De cette façon, vous finiriez par détruire votre "autoroute neurale" existante (qui produisait le code que vous écrivez maintenant) et créera une nouvelle "autoroute neurale" qui produirait le code de clojure magnifique et idiomatique. Essayez également de ne pas sauter pour taper du code dès que vous avez vu un problème, donnez-vous plutôt du temps pour réfléchir clairement et profondément sur le problème et les solutions.
