Tree traversal with corecursion

Question

I'm trying to figure out corecursion in Clojure with nontrivial (i.e. not Fibonacci), but manageable, examples. Apparently it is possible to implement binary tree traversal with corecursion. Wikipedia has an example in Python which I am unable to understand.

How can I implement it in Clojure? Let's say I'm looking for BFS, but it could be any order.

Here's what I have so far:

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

Unfortunately it seems to be going all the way to the left, ignoring the right branch.

Answer 1

Here is a direct translation of the bftrav Haskell function from the Wikipedia article. Note that it uses a letrec macro I've just written -- see this Gist for the latest version.

I've changed your definition of my-tree to read thus:

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

Also, my leaf? function assumes that we're only dealing with proper two-way branches and leaf nodes (so a nil on the :left branch implies a nil on the :right branch); it shouldn't be two difficult to change this to handle single-child "branches":

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

The code for bftrav is as follows:

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

An example from the 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

Answer 2

Assuming Michal's code does what you want, this also works:

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