Обход дерева с corecursion

Question

Я пытаюсь выяснить, что корунсирование в Clojure с нетривиальным (т. Е. Не Фибоначчи), но управляемыми примерами. По-видимому, можно реализовать двоичный обход дерева с помощью корекурсии. В Википедии есть пример в Python, который я не могу понять.

Как я могу реализовать его в Clojure? Предположим, я ищу BFS, но это может быть любой порядок.

Вот что я до сих пор:

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

К сожалению, это, кажется, пройдя весь путь налево, не обращая внимания на правую ветвь.

Answer 1

Предполагая, что код Michal в делает то, что вы хотите, это также работает:

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

Answer 2

Прямой перевод функции bftrav Haskell из Википедии. Обратите внимание, что он использует макрос letrec, который я только что написал - см. this Gist для последней версии.

Я изменил ваше определение my-tree читать следующим образом:

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

Кроме того, моя leaf? функция предполагает, что мы имеем дело только с соответствующими двухсторонними ветвей и листьев узлов (так nil на :left ветвь подразумевает nil на ветке :right); это не должно быть два трудно изменить для обработки одного ребенка «ветви»:

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

Код для bftrav выглядит следующим образом:

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

Пример из РЕПЛ:

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