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

Question

Я пытаюсь выяснить corecursion в Clojure с нетривиальными (то есть не Фибоначчи), но управляемыми примерами.По-видимому, можно реализовать обход двоичного дерева с помощью corecursion.В Википедии есть пример на 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

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

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

Пример из 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