Este equipo de especialistas luego de muchos días de trabajo y de recopilar de información, dieron con los datos necesarios, queremos que te sea útil en tu proyecto.
Solución:
1. ¿Por qué su función cola no es recursiva?
Para que una función recursiva sea recursiva en cola, todas las llamadas recursivas deben estar en posición de la cola. Una función está en la posición final si es lo último que se llama antes de que la función regrese. En tu primer ejemplo tienes
depth (Branch _ l r) = 1 + max (depth l) (depth r)
que es equivalente a
depth (Branch _ l r) = (+) 1 (max (depth l) (depth r))
La última función llamada antes de que regrese la función es (+), por lo que esta cola no es recursiva. En tu segundo ejemplo tienes
depthTR d (Branch _ l r) = let dl = depthTR (d+1) l
dr = depthTR (d+1) r
in max dl dr
que es equivalente a (una vez que haya vuelto a lambdificar todos los let declaraciones) y reorganizado un poco
depthTR d (Branch _ l r) = max (depthTR (d+1) r) (depthTR (d+1) l)
Ahora la última función llamada antes de regresar es max, lo que significa que tampoco se trata de una cola recursiva.
2. ¿Cómo podrías hacer que la cola sea recursiva?
Puede hacer una función recursiva de cola usando estilo de continuación-pase. En lugar de reescribir su función para tomar un estado o un acumulador, pasa una función (llamada continuación) que es una instrucción sobre qué hacer con el valor calculado, es decir, en lugar de regresar inmediatamente a la persona que llama, pasa cualquier valor que haya calculado a la continuación. Es un truco fácil para convertir cualquier función en una función recursiva de cola, incluso funciones que necesitan llamarse a sí mismas varias veces, como depth lo hace. Se parece a esto
depth t = go t id
where
go Empty k = k 0
go (Branch _ l r) k = go l $ dl ->
go r $ dr ->
k (1 + max dl dr)
Ahora ves que la última función llamada en go antes de que regrese es él mismo go, por lo que esta función es recursiva al final.
3. ¿Entonces es eso?
(Nota: esta sección se basa en las respuestas a esta pregunta anterior).
¡No! Este “truco” sólo empuja el problema a otra parte. En lugar de una función recursiva sin cola que usa mucho espacio de pila, ahora tenemos una función recursiva con cola que come thunks (funciones no aplicadas) que potencialmente podrían estar ocupando mucho espacio por sí mismos. Afortunadamente, no necesitamos trabajar con funciones arbitrarias; de hecho, solo hay tres tipos
dl -> go r (dr -> k (1 + max dl dr))(que usa las variables libresryk)dr -> k (1 + max dl dr)(con variables libreskydl)id(sin variables libres)
Dado que solo hay un número finito de funciones, podemos representarlas como datos
data Fun a = FunL (Tree a) (Fun a) -- the fields are 'r' and 'k'
| FunR Int (Fun a) -- the fields are 'dl' and 'k'
| FunId
Tendremos que escribir una función eval también, que nos dice cómo evaluar estas “funciones” en argumentos particulares. Ahora puede volver a escribir la función como
depth t = go t FunId
where
go Empty k = eval k 0
go (Branch _ l r) k = go l (FunL r k)
eval (FunL r k) d = go r (FunR d k)
eval (FunR dl k) d = eval k (1 + max dl d)
eval (FunId) d = d
Tenga en cuenta que ambos go y eval tener llamadas a cualquiera go o eval en posición de cola, por lo que son un par de mutuamente cola recursiva funciones. Así que hemos transformado la versión de la función que usaba el estilo de paso de continuación en una función que usa datos para representar continuaciones y usa un par de funciones recursivas entre sí para interpretar esos datos.
4. Eso suena realmente complicado
Bueno, supongo que lo es. ¡Pero espera! ¡Podemos simplificarlo! Si miras el Fun a tipo de datos, verá que en realidad es solo una lista, donde cada elemento es un Tree a que vamos a calcular la profundidad, o es un Int que representa una profundidad que hemos calculado hasta ahora.
¿Cuál es el beneficio de notar esto? Bueno, esta lista en realidad representa el pila de llamadas de la cadena de continuaciones de la sección anterior. ¡Insertar un nuevo elemento en la lista es insertar un nuevo argumento en la pila de llamadas! Para que pudieras escribir
depth t = go t []
where
go Empty k = eval k 0
go (Branch _ l r) k = go l (Left r : k)
eval (Left r : k) d = go r (Right d : k)
eval (Right dl : k) d = eval k (1 + max dl d)
eval [] d = d
Cada nuevo argumento que empuja a la pila de llamadas es de tipo Either (Tree a) Int, y a medida que las funciones se repiten, siguen introduciendo nuevos argumentos en la pila, que son nuevos árboles para explorar (siempre que go se llama) o la profundidad máxima encontrada hasta ahora (siempre que eval se llama).
Esta estrategia de llamada representa un recorrido en profundidad del árbol, como puede ver por el hecho de que el árbol de la izquierda siempre es explorado primero por go, mientras que el árbol de la derecha siempre se inserta en la pila de llamadas para explorarlo más tarde. Los argumentos solo se extraen de la pila de llamadas (en eval) cuando un Empty Se ha alcanzado la rama y se puede descartar.
5. Muy bien … ¿algo más?
Bueno, una vez que haya notado que puede convertir el algoritmo de paso de continuación en una versión que imita la pila de llamadas y atraviesa la profundidad del árbol primero, puede comenzar a preguntarse si hay un algoritmo más simple que atraviesa la profundidad del árbol primero, haciendo un seguimiento de la profundidad máxima encontrada hasta ahora.
Y de hecho, lo hay. El truco consiste en mantener una lista de las ramas que aún no ha explorado, junto con sus profundidades, y realizar un seguimiento de la profundidad máxima que ha visto hasta ahora. Se parece a esto
depth t = go 0 [(0,t)]
where
go depth [] = depth
go depth (t:ts) = case t of
(d, Empty) -> go (max depth d) ts
(d, Branch _ l r) -> go (max depth d) ((d+1,l):(d+1,r):ts)
Creo que eso es tan simple como puedo hacer que esta función funcione dentro de las limitaciones de asegurar que sea recursiva en la cola.
6. ¿Entonces eso es lo que debería usar?
Para ser honesto, su versión original, no recursiva de cola probablemente esté bien. Las nuevas versiones no son más eficientes en cuanto al espacio (siempre tienen que almacenar la lista de árboles que va a procesar a continuación) pero tienen la ventaja de almacenar los árboles que se procesarán a continuación en el montón, en lugar de en la pila, y hay mucho más espacio en la pila.
Es posible que desee ver la función parcialmente recursiva de cola en la respuesta de Ingo, que ayudará en el caso de que sus árboles estén extremadamente desequilibrados.
Una versión parcialmente recursiva de cola sería la siguiente:
depth d Empty = d
depth d (Branch _ l Empty) = depth (d+1) l
depth d (Branch _ Empty r) = depth (d+1) r
depth d (Branch _ l r) = max (depth (d+1) l) (depth (d+1) r)
Tenga en cuenta que la reanudación de la cola en este caso (a diferencia del caso completo más complejo en la respuesta de Chris) se realiza solo para omitir las ramas incompletas.
Pero esto debería ser suficiente asumiendo que la profundidad de sus árboles es como máximo un número de dos dígitos. De hecho, si equilibra adecuadamente su árbol, esto debería estar bien. Si sus árboles, OTOH, se degeneran en listas, esto ya ayudará a evitar el desbordamiento de la pila (esta es una hipótesis que no he probado, pero ciertamente es true para un árbol totalmente degenerado que no tiene rama con 2 hijos no vacíos).
La recursividad de la cola no es una virtud en sí misma. Solo entonces es importante si no queremos explotar la pila con lo que sería un bucle simple en lenguajes de programación imperativos.
a su 3., sí, por ejemplo, mediante el uso de la técnica CPS (como se muestra en la respuesta de Chris);
a su 4., correcto.
a su 2., con el recorrido del árbol primero en amplitud corecursiva perezosa obtenemos naturalmente una solución similar a la última de Chris (es decir, su recorrido # 5., primero en profundidad con pila explicada), incluso sin ninguna llamada a max:
treedepth :: Tree a -> Int
treedepth tree = fst $ last queue
where
queue = (0,tree) : gen 1 queue
gen 0 p = []
gen len ((d,Empty) : p) = gen (len-1) p
gen len ((d,Branch _ l r) : p) = (d+1,l) : (d+1,r) : gen (len+1) p
Aunque ambas variantes tienen una complejidad espacial de O (n) en el peor de los casos, los peores casos en sí son diferentes, y opuesto entre sí: los árboles más degenerados son el peor caso para el recorrido en profundidad primero (DFT) y el mejor caso (en el espacio) para el ancho primero (BFT); y de manera similar, los árboles más equilibrados son el mejor caso para DFT y el peor para BFT.
Te invitamos a añadir valor a nuestra información asistiendo con tu veteranía en las notas.