haskell - ¿Hay alguna manera de reducir el dolor del seguimiento de rango?

data-structures patricia-trie

Question

Actualmente hay una solicitud de extracción por parte de Jonathan S. para reemplazar la implementación de Data.IntMap con una explicada en este Data.IntMap README basada en las ideas de una publicación de blog de Edward Kmett.

El concepto básico del que se desarrolló Jonathan S. es que un IntMap es un árbol binario que se ve así (hice algunos pequeños cambios en su desarrollo en aras de la coherencia):

data IntMap0 a = Empty | NonEmpty (IntMapNE0 a) 
data IntMapNE0 a =
    Tip !Int a
  | Bin { lo :: !Int
        , hi :: !Int
        , left :: !(IntMapNE0 a)
        , right :: !(IntMapNE0 a) }

En esta representación, cada nodo tiene un campo que indica la clave menor y mayor contenida en el IntMapNE0 . Usar solo un poco de toque permite que esto sea usado como un trie PATRICIA. Jonathan señaló que esta estructura tiene casi el doble de información de rango que necesita. Seguir una espina dorsal izquierda o derecha producirá todos los mismos límites lo o hi . Entonces los eliminó solo incluyendo el límite no determinado por los antepasados:

data IntMap1 a = Empty | NonEmpty { topLo :: !Int, child :: !(IntMapNE1 a) }
data IntMapNE1 a =
    Tip a
  | IntMapNE1 { bound :: !Int
              , left :: !(IntMapNE1 a)
              , right :: !(IntMapNE1 a)

Ahora cada nodo tiene un límite izquierdo o un límite derecho, pero no ambos. Un niño derecho solo tendrá un límite izquierdo, mientras que un niño izquierdo solo tendrá un límite derecho.

Jonathan hace un cambio adicional, moviendo los valores de las hojas hacia los nodos internos, lo que los ubica exactamente donde están determinados. También usa tipos fantasmas para ayudar a rastrear a la izquierda y a la derecha. El tipo final (por ahora, de todos modos) es

data L
data R
newtype IntMap a = IntMap (IntMap_ L a) deriving (Eq)
data IntMap_ t a = NonEmpty !Int a !(Node t a) | Empty deriving (Eq)
data Node t a = Bin !Int a !(Node L a) !(Node R a) | Tip deriving (Eq, Show)

Ciertos aspectos de esta nueva implementación son bastante atractivos. Lo más importante es que muchas de las operaciones más utilizadas son sustancialmente más rápidas. Menos importante, pero muy bien, el truco poco involucrado es mucho más fácil de entender.

Sin embargo, hay un punto de dolor serio: pasar la información del rango faltante a través del árbol. Esto no es tan malo para búsquedas, inserciones, etc., pero se pone bastante peludo en el código de unión e intersección. ¿Hay alguna abstracción que permita que esto se haga automáticamente?

Un par de pensamientos extremadamente vagos:

1. ¿Podrían los tipos fantasmas usarse con una clase personalizada para vincular el tratamiento directamente con la destreza?

2. La naturaleza de "pieza faltante" recuerda un poco a algunas situaciones con cremallera. ¿Podría haber alguna manera de usar ideas de ese reino?

Empecé a pensar en usar un tipo intermedio de algún tipo para proporcionar una "vista" simétrica de la estructura, pero estoy un poco atascado. Puedo convertir fácilmente entre la estructura básica y la de lujo, pero esa conversión es recursiva. Necesito una forma de convertir solo parcialmente, pero no sé lo suficiente sobre los tipos construidos fantásticamente para hacerlo.

Answer 1

¿Hay alguna abstracción que permita que esto se haga automáticamente?

Debería poder definir un conjunto de sinónimos de patrones que le den eso. Comenzaré desde la penúltima variante de tu código, es decir:

data IntMap1 a = Empty | NonEmpty { topLo :: !Int, child :: !(IntMapNE1 a) }
data IntMapNE1 a =
    Tip a
  | IntMapNE1 { bound :: !Int
              , left :: !(IntMapNE1 a)
              , right :: !(IntMapNE1 a)

Tuplamos dicho valor con el límite del padre en un Either (que indica si se trata de un límite alto o bajo).

viewLoHi (Left lo, IntMapNE1 hi left right)
    = Just (lo, hi, (Left lo, left), (Right hi, right)
viewLoHi (Right hi, IntMapNE1 lo left right)
    = Just (lo, hi, (Left lo, left), (Right hi, right)
viewLoHi _
    = Nothing

pattern Bin'' lo hi left right <- (viewLoHi -> Just (lo, hi, left, right))

El tipo de datos de nivel superior es diferente, por lo que necesita su propio sinónimo de patrón

viewLoHi'' (NonEmpty lo child) = viewLoHi (Left lo, child)
viewLoHi'' Empty = Nothing

pattern NonEmpty'' lo hi left right <- (viewLoHi'' -> Just (lo, hi, left, right)

Al usar solo NonEmpty'' y Bin'' mientras recorre el árbol, la contabilidad ahora debe estar completamente oculta. (Código no probado, por lo que habrá errores tipográficos aquí)