Skip to content

Instantly share code, notes, and snippets.

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

Creo que ahora, siguiendo la implementacion de
http://www.enrico-franchi.org/2011/02/callcc-i-yield-bah-lazy-seq.html
La cuestion es no bifurcar la llamada recursiva dentro de lazy-seq para evitar lo que tu comentabas, sino ir metiendo los nodos a tratar en la cima de la secuencia que se va construyendo/consumiendo. No se si me explico bien.
Asi he conseguido que no salte la pila, ahora se queda colgado con (when-not (zero? (rand-int 3))) :-P

@vemv
Copy link

vemv commented Apr 23, 2012

pues sí, funciona, y más rápido que la implementación anterior. y sin volar la pila, efectivamente. sorprende que como dice federico, la llamada a aux no es recursiva.

quizá de lo más retorcido que haya visto hasta ahora. rico rico ;p

de lo que parece que no estamos seguros es de si to-seq no responde a partir de valores grandes (pasándole a test un range de 1000, por ejemplo) por encontrarse con un árbol 'en racha', o por que el algoritmo tenga un rendimiento peor que lineal.

ps - rand-tree-node se refiere a seed.

@jneira
Copy link
Author

jneira commented Apr 23, 2012

Si que es curioso.
Sin embargo yo no diria que lazy-seq hace que no sea recursiva (como afirma Enrico) la llamada sino que la interrumpe devolviendo el control al codigo llamador. Para mi sigue siendo recursiva "semanticamente" o a nivel de diseño del algoritmo aunque no su implementacion interna. Sobre todo porque las funciones que usan lazy seqs "reestablecen" de alguna manera la recursividad de forma transparente para el programador.
Si te fijas al final hay que usar una pila en el heap para evitar copar la pila de llamadas de forma muy similar a lo que habria que hacer con un algoritmo imperativo, aunque se puede mantener la recursividad no final si la llamada recursiva es unica. La diferencia es que en lugar de mutar la pila la vas generando a golpe de llamadas consecutivas y almacenandola en la cola de la lazy-seq a la vez que la consumes.
La verdad que las pocas veces que he usado lazy-seq no me habia encontrado el caso y se me antoja que lo devalua ya que no puedes separar el ser lazy de como esta diseñado el algoritmo al que se llama dentro de el (o sea la semantica de la implementacion interna).
No me di cuenta que al mantener varias llamadas recursivas lazy-seq devolvia el control de nuevo al mismo codigo que esta dentro de lazy-seq con lo que la pila no se quedaba libre...aiiins.
En cuanto a mis divagaciones:

  • Si hicieramos descender al arbol de LazySeq o al crear arboles sucesivos el problema lo tendriamos igual en diferente sitio (o en el mismo) y la solucion tendria que ser muy similar.
  • Me he puesto a trasladar el codigo a haskell como curiosidad de ver como se comporta en este caso.

@vemv
Copy link

vemv commented Apr 23, 2012

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'...

@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