Traversal de árbol con corecursion

Estoy intentando averiguar corecursion en Clojure con ejemplos no triviales (es decir, no Fibonacci) pero manejables. Aparentemente es posible implementar el cruce de árbol binario con corecursion. Wikipedia tiene un ejemplo en Python que no puedo entender.Traversal de árbol con corecursion

¿Cómo puedo implementarlo en Clojure? Digamos que estoy buscando BFS, pero podría ser cualquier orden.

Esto es lo que tengo hasta ahora:

(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))

Por desgracia, parece ir todo el camino a la izquierda, haciendo caso omiso de la rama derecha.

Fuente

2010-07-22 Konrad Garus

¿Puedes vincular al código python o dar más detalles sobre qué es exactamente lo que intentas hacer con el código? Pegar código roto no proporciona suficiente información. ;) En una nota potencialmente relacionada, 'letfn' proporciona una forma de hacer la recursión mutua. –

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

Datos insuficientes para una respuesta significativa. –

Suponiendo código de Michal hace lo que quiere, esto también funciona:

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

Fuente

2010-07-23 06:33:14

Esto es tan bueno ... +1. Podría reemplazar '# (vector ...)' con '(juxt: izquierda: derecha)' para hacerlo aún más bonito. :-) –

Y el otro día solo me decía a mí mismo: "¿Para qué sirve el juxt?" ¡Excelente! –

¿No ejecuta bftrav una y otra vez para los mismos nodos en cada iteración? –

Aquí hay una traducción directa de la función bftrav Haskell del artículo de Wikipedia. Tenga en cuenta que utiliza una macro letrec que acabo de escribir; consulte this Gist para obtener la última versión.

he cambiado su definición de my-tree para leer así:

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

Además, mi función leaf? asume que sólo estamos tratando con ramas de dos vías adecuadas y nodos hoja (por lo que un nil en el :left rama implica un nil en la rama :right); no debe ser de dos difíciles de cambiar este para manejar "ramas" de un solo hijo:

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

El código para bftrav es como sigue:

(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 ejemplo 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

Fuente

2010-07-23 05:34:10

Traversal de árbol con corecursion

Respuesta

Cuestiones relacionadas