Traversée d'arbres avec corecursion

J'essaie de comprendre la corécursion dans Clojure avec des exemples non triviaux (c'est-à-dire non-Fibonacci), mais gérables. Apparemment, il est possible d'implémenter une traversée d'arbre binaire avec corecursion. Wikipedia a un exemple en Python que je suis incapable de comprendre.Traversée d'arbres avec corecursion

Comment puis-je l'implémenter dans Clojure? Disons que je suis à la recherche de BFS, mais cela pourrait être n'importe quel ordre.

Voici ce que j'ai jusqu'à présent:

(defstruct tree :val :left :right) 

(def my-tree (struct tree 1 (struct tree 2) (struct tree 3 4 5))) 

(def bfs (lazy-cat [my-tree] (map #(:left %) bfs) (map #(:right %) bfs))) 

(println (take 4 bfs))

Malheureusement, il semble aller tout le chemin à gauche, en ignorant la branche droite.

Source

2010-07-22 Konrad Garus

Pouvez-vous lier au code python, ou donner plus de détails sur ce que vous essayez exactement de faire le code? Coller du code cassé ne fournit pas suffisamment d'informations. ;) Sur une note potentiellement liée, 'letfn' fournit un moyen de faire une récurrence mutuelle. –

@ataggart: http://en.wikipedia.org/wiki/Corecursion –

Données insuffisantes pour une réponse significative. –

En supposant le code de Michal fait ce que vous voulez, cela fonctionne aussi:

(defn bftrav [& trees] 
    (when trees 
    (concat trees 
     (->> trees 
     (mapcat #(vector (:left %) (:right%))) 
     (filter identity) 
     (apply bftrav)))))

Source

2010-07-23 06:33:14

C'est tellement beau ... +1. Vous pouvez remplacer '# (vector ...)' par '(juxt: left: right)' pour le rendre encore plus joli. :-) –

Et je me disais juste l'autre jour, "à quoi bon juxt?" Excellent! –

N'exécute-t-il pas bftrav encore et encore pour les mêmes nœuds dans chaque itération? –

Voici une traduction directe de la fonction Haskell bftrav de l'article Wikipedia. Notez qu'il utilise une macro letrec que je viens d'écrire - voir this Gist pour la dernière version.

J'ai changé votre définition de my-tree lire ainsi:

(def my-tree (struct tree 1 (struct tree 2) (struct tree 3 (struct tree 4) (struct tree 5))))

En outre, ma fonction leaf? suppose que nous ne traitons avec les branches appropriées dans les deux sens et les nœuds de feuilles (donc un nil sur la :left branche implique un nil sur la branche :right); il ne devrait pas être deux difficiles à changer cela pour gérer un seul enfant "branches":

(defn leaf? [t] (nil? (:left t)))

Le code pour bftrav se présente comme suit:

(defn bftrav [t] 
    (letrec [queue (lazy-seq (cons t (trav 1 queue))) 
      trav (fn [l q] 
        (lazy-seq 
        (cond (zero? l) nil 
          (leaf? (first q)) (trav (dec l) (rest q)) 
          :else (let [{:keys [left right]} (first q)] 
            (cons left (cons right (trav (inc l) (rest q))))))))] 
    queue))

Un exemple de la REPL:

user> (bftrav my-tree) 
({:val 1, :left {:val 2, :left nil, :right nil}, :right {:val 3, :left {:val 4, :left nil, :right nil}, :right {:val 5, :left nil, :right nil}}} {:val 2, :left nil, :right nil} {:val 3, :left {:val 4, :left nil, :right nil}, :right {:val 5, :left nil, :right nil}} {:val 4, :left nil, :right nil} {:val 5, :left nil, :right nil}) 
user> (count (bftrav my-tree)) 
5

Source

2010-07-23 05:34:10

Traversée d'arbres avec corecursion

Répondre

Questions connexes