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

oops 'federico', qué mal.

Como observación tonta, da un gustazo quitar 'lazy-seq' y ver cómo en ese caso el algoritmo falla. en plan ohhhhh, funciona jajaja.

viendo de nuevo el código, hay algo que no entiendo. por qué 'lazy-seq' parecer incluir el valor de 'expand' dos veces? si fuera nil por ejemplo, iría tanto por 'vals' como por 'cons'...

Hace ilusion sacar el conejo de la chistera incluso aunque conozcas el truco.
En cuanto a los nil, no se repiten ya que (= (vals nil) nil) y (= (concat nil (2)) '(2)). Asi aparecen en la secuencia de nodos como hojas al contrario que en el ejemplo que los elimima con (keep identity)

pues sí, no había caído en ese detalle sobre concat que ciertamente tiene sentido por parte de Rich.

ahora la otra parte del misterio... un caso típico parece que evaluarîa a (cons {:left seed :right seed} (aux (concat '(seed seed) (rest s)). no estaríamos duplicando referencias a seed aquí?

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