rand_tree.clj

(ns rand-tree)

(defn seed []
  (let [r #(when (zero? (rand-int 2)) seed)]
    {:left (r)
     :right (r)}))

(def seed? fn?)
(def leaf? nil?)
(def branch? map?)

;; see http://www.enrico-franchi.org/2011/02/callcc-i-yield-bah-lazy-seq.html
(defn to-seq [tree]
  (letfn
   [(aux [stack]
         (if-let [s (seq stack)]
           (let [node (first s)
                 expand (if (seed? node) (node) node)
                 nxt #(aux (concat (vals expand) (rest s)))]
             (lazy-seq (cons expand (nxt))))
           '()))]
   (aux [tree])))

;; using standar tree-seq you can get a stackoverflow
(defn core-to-seq [root]
  (tree-seq branch? #(for [v (vals %)] (when v (v))) root))

(defn test []
  (for [i (range 100)
	:let [c (count (to-seq seed))]
	:when (> c 100)]
    c))

Sim pero cada seed es una funcion que genera potencialmente mas nodos, diferentes cada vez cuando le toca ser procesado. Si solo ponemos uno no expandimos el arbol entero sino solo una de las ramas.
Como sospechaba en haskell no hace falta hacer nada especial para que no salte la stack. Usa unfoldTree para generar el arbol y con probabilidades altas de generar hijos se queda colgado calculando.
https://gist.github.com/2477668