haskell - programacion - ¿Qué árbol de equilibrio automático es el más simple en la programación funcional?

programacion funcional haskell

Question

Estoy diseñando un árbol de auto equilibrio en Haskell. Como ejercicio y porque es bueno tenerlo en tu mano trasera.

Anteriormente, en C y en Python, prefería las golosinas y los árboles de distribución debido a sus simples reglas de equilibrio. Siempre me disgustaron los árboles R / B, ya que parecían más trabajo del que valían.

Ahora, debido a la naturaleza funcional de Haskell, las cosas parecen haber cambiado. Puedo escribir una función de inserción R / B en 10 líneas de código. Las golosinas, por otro lado, requieren una envoltura para almacenar el generador de números aleatorios, y los árboles de distribución son un dolor para hacer de arriba hacia abajo.

¿Entonces te pregunto si tienes experiencia con otros tipos de árboles? ¿Cuáles son mejores para utilizar la coincidencia de patrones y la naturaleza descendente de los lenguajes funcionales?

Answer 1

Como dices, los árboles rojo negro no son tan difíciles de usar. ¿Le has echado un vistazo a los árboles de dedos ? Es posible que esté interesado en aumentar su estructura de datos base con algo como una zipper. Otro árbol que podría encontrar interesante es el árbol AA, que es una simplificación de los árboles negros y rojos.

Answer 2

Es el que ya está implementado.

Hay implementaciones finas en Haskell de árboles equilibrados como Data.Map y Data.Set. ¿No satisfacen tus necesidades? No reimplementar, reutilizar.

Answer 3

La biblioteca estándar de OCaml utiliza un árbol AVL para su functor de map . Parece que es más fácil de implementar que un árbol RB si se incluye una operación de remove .

Answer 4

Ok, supongo que no hubo muchas referencias o investigaciones para responder esta pregunta. En su lugar, me he tomado el tiempo para probar sus diferentes ideas y árboles. No encontré nada mejor que los árboles RB, pero tal vez eso es solo sesgo de búsqueda.

El árbol RB puede ser (inserción) equilibrado con cuatro reglas simples, como lo muestra Chris Okasaki :

balance T (T R (T R a x b) y c) z d = T R (T B a x b) y (T B c z d)
balance T (T R a x (T R b y c)) z d = T R (T B a x b) y (T B c z d)
balance T a x (T R b y (T R c z d)) = T R (T B a x b) y (T B c z d)
balance T a x (T R (T R b y c) z d) = T R (T B a x b) y (T B c z d)
balance T a x b = T B a x b

Los árboles AVL se pueden equilibrar de forma similar a la de un patrón. Sin embargo, las reglas no se comprimen tan bien:

balance T (T (T a x b   dx) y c (-1)) z d (-2) = T (T a x b dx) y (T c z d  0) 0
balance T a x (T b y (T c z d   dz)   1 )   2  = T (T a x b  0) y (T c z d dz) 0
balance T (T a x (T b y c   1 )   1 ) z d (-2) = T (T a x b -1) y (T c z d  0) 0
balance T (T a x (T b y c (-1))   1 ) z d (-2) = T (T a x b  0) y (T c z d  1) 0
balance T (T a x (T b y c   _ )   1 ) z d (-2) = T (T a x b  0) y (T c z d  0) 0
balance T a x (T (T b y c   1 ) z d (-1))   2  = T (T a x b -1) y (T c z d  0) 0
balance T a x (T (T b y c (-1)) z d (-1))   2  = T (T a x b  0) y (T c z d  1) 0
balance T a x (T (T b y c   _ ) z d (-1))   2  = T (T a x b  0) y (T c z d  0) 0
balance t = t

Como las costuras de los árboles AVL generalmente se consideran inferiores a las de los árboles RB, probablemente no valen la pena la molestia adicional.

Los árboles de AA podrían teóricamente equilibrarse de forma agradable y sencilla mediante:

balance T n (T n a x b) y c = T n a x (T n b y c) -- skew
balance T n a x (T n b y (T n c z d)) = T (n+1) (T n a x b) y (T n c z d) --split
balance T n a x b = T n a x b

Pero, desafortunadamente, a Haskell no le gusta la sobrecarga de n . Es posible que una implementación menos estándar de árboles AA, que no usa rangos, pero algo más similar a R y B, funcione bien.

Los árboles de distribución son difíciles porque necesita enfocarse en un solo nodo, en lugar de en la estructura estática del árbol. Se puede hacer combinando inserto y espacio .

Las asas también son difíciles de realizar en un entorno funcional, ya que no tiene un generador aleatorio global, pero necesita mantener instancias en cada nodo. Esto se puede abordar dejando la tarea de generar prioridades para el cliente , pero incluso en ese caso, no puede hacer una comparación de prioridades utilizando la coincidencia de patrones.