Skip to content

Instantly share code, notes, and snippets.

@jneira
Created Apr 18, 2012
Embed
What would you like to do?
(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))
@vemv
Copy link

vemv commented Apr 18, 2012

"de depth" :) yo también suelo cometer ese error!

en principio sí, cuela, de hecho no se me había ocurrido jajaja. pero no sirve para el propósito del programa, que debería haberme molestado en explicar.

todo viene a cuento de la observación de que los resultados de (count-nodes (rand-tree)) parecen ser bastante "extremos": o bien 1-30 nodos, o pasados los 1000. la visualización mediante barras etc en principio confirma esto.

pero usar aleatoridad limitada por desbordamientos de pila no es lo que se dice riguroso. se me ocurre que uno podría crear árboles mutando pilas del heap, como acabo de encontrar aquí http://stackoverflow.com/a/547636/569050 - no quedaría elegante en todo caso. o sí?

saludos javier.

@jneira
Copy link
Author

jneira commented Apr 18, 2012

Efectiavmente la solucion "imperativa" parece que pasa necesariamente por usar la pila.
No se si habias visto la version usando tree-seq cuando has puesto el comentario...

@vemv
Copy link

vemv commented Apr 18, 2012

esta tarde me pongo, tree-seq suena muy apetecible. la parte de (zero? (rand-int 2)) queda mejor llamada como una función, de otro modo ambas llamadas reciben el mismo valor.

@jneira
Copy link
Author

jneira commented Apr 18, 2012

Oooops, cierto, con ello se falsea la observacion.
Normalmente tree-seq se usar para generar una secuencia de los nodos de un arbol previamente creado en lugar de generar los nodos al vuelo pero creo que asi vale para contarlos.
He añadido una funcion que genera el arbol real con su estructura como hace rand-tree en un paso. Como ella, tambien falara con stack overflows

@vemv
Copy link

vemv commented Apr 20, 2012

Creo entenderlo todo. En principio parece que tree-seq y cia no arreglan mucho, pero en todo caso ha merecido la pena añadir trucos nuevos a la 'chistera'.

El concepto de zipper es atractivo, los ejemplos de clojure.org me resultaron especialmente esclarecedores.

@jneira
Copy link
Author

jneira commented Apr 20, 2012

Mmm ¿pero rand-tree-seq contiene los nodos de un arbol aleatorio y el contarlos no provoca stackoverflows no? tal vez se me escapa algo que es necesario para que la observacion sea correcta...

@vemv
Copy link

vemv commented Apr 20, 2012

Si se baja la probabilidad de que un nodo sea nil, es fácir provocar un desbordamiento:

(defn rand-tree-node []
  (let [r #(when-not (zero? (rand-int 3)) rand-tree-node)]
    {:left (r)
     :right (r)}))

(test)

@jneira
Copy link
Author

jneira commented Apr 20, 2012

Arrrgh cierto, no habia visto la implementacion de tree-seq, y aunque crea la lista de nodos de forma perezosa la funcion que visita los nodos del arbol para ir añadiendolos (y que en este caso los genera) es recursiva :-/
(Editado: que sea recursiva no es el problema ya que lazy-seq hace que la recursividad no se apoye en la stack)

@vemv
Copy link

vemv commented Apr 20, 2012

Yo creo que es inherente a los árboles el que siempre quede "trabajo pendiente" (a saber: los nodos derechos) y que por lo tanto no pueda trabajarse con ellos ilimitadamente (puede que me equivoque).

En todo caso tu implementación parece que resuelve el problema originalmente planteado, generar árboles con un "factor" de dos sin desbordar.

@jneira
Copy link
Author

jneira commented Apr 20, 2012

No me quedo tranquilo ;-)
Tal vez en haskell si que seria posible ya que todos los tipos son perezosos, y en clojure tal vez tambien creando un nuevo tipo que descienda de LazySeq pero que se ajuste a la estructura del arbol.
Otra idea seria ir generando de forma perezosa arboles usando para cada uno el anterior y expandir solo una vez cada "semilla" (nodo con la funcion rand-tree-node) mientras haya nodos con "semillas". Sin embargo me da que al hacerlo asi el rendimiento seria muy bajo.

@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