Skip to content

Instantly share code, notes, and snippets.

@jneira
Created April 18, 2012 05:23
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save jneira/2411257 to your computer and use it in GitHub Desktop.
(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))
@jneira
Copy link
Author

jneira commented Apr 23, 2012

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)

@vemv
Copy link

vemv commented Apr 23, 2012

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í?

@jneira
Copy link
Author

jneira commented Apr 24, 2012

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment