Encuentre las claves más cercanas a un argumento entero en el árbol de Haskell

2
Max_ReFactor 2019-12-14 15:44.

Hay muchas soluciones sobre cómo encontrar las claves inferiores y superiores más cercanas en el árbol binario en lenguajes imperativos, pero faltan las mismas preguntas para hacerlo en un estilo puramente funcional como el de Haskell. Tengo curiosidad por saber cómo es posible caminar alrededor de un árbol de búsqueda binario antes de encontrar las dos claves más cercanas. Hay una función y algunas coincidencias de patrones que tengo hasta ahora:

data TreeMap v = Leaf | Node { pair::(Integer, v), l::TreeMap v, r::TreeMap v} deriving (Show, Read, Eq, Ord)

closestLess :: Integer -> TreeMap v -> (Integer, v)
closestLess i Leaf = error "Tree doesn't include any element"
closestLess i (Node pair tree_r tree_l)
        | i < fst pair = closestLess i tree_l
        | i == fst pair = closestLess i tree_r
        | otherwise = precise i pair tree_r 

Utilizo esta función para obtener una clave más baja, pero más cercana a un argumento Integer. En mi opinión, no hay nada más que la necesidad de implementar alguna función auxiliar como "precisa", aunque estoy confundido sobre qué definición necesita exactamente. Mi sugerencia es poner ese valor entero, nodo en el subárbol derecho "preciso" también para encontrar cualquier clave que esté más cerca del objetivo. Por lo tanto, también tendría algunos consejos o suposiciones sobre cómo hacerlo para las teclas inferiores y superiores.

1 answers

0

Así es como lo haría:

data TreeMap v = Leaf | Node Integer v (TreeMap v) (TreeMap v) deriving (Show, Read, Eq, Ord)

closestLess :: Integer -> TreeMap v -> Maybe (Integer, v)
closestLess i = precise Nothing where
  precise :: Maybe (Integer, v) -> TreeMap v -> Maybe (Integer, v)
  precise closestSoFar Leaf = closestSoFar
  precise closestSoFar (Node k v l r) = case i `compare` k of
    LT -> precise closestSoFar l
    EQ -> Just (k, v)
    GT -> precise (Just (k, v)) r

Algunas notas sobre las diferencias entre esto y su intento:

  • Usó la sintaxis de registro para el Nodeconstructor. Es una mala forma utilizar la sintaxis de registro en tipos de suma, ya que las funciones serían parciales (por ejemplo, pair Leafestarían al final). Como en realidad no usaste estos y no son necesarios, los eliminé.
  • Envolvió la clave y el valor en una tupla, sin ninguna razón aparente. Los separé y los coloqué directamente en el tipo.
  • Su closestLessfunción tenía un tipo de retorno de (Integer, v), aunque no siempre podía devolver algo de ese tipo. Lo cambié a Maybe (Integer, v), para que pueda regresar en Nothinglugar de tener que usarlo error. (Nota al margen: su mensaje de error era técnicamente incorrecto. Si llamó closestLessdonde el valor de búsqueda es más pequeño que todos los nodos, fallaría aunque el árbol tuviera elementos).
  • Su código es inconsistente en cuanto a cuál es la rama izquierda y cuál es la rama derecha de los nodos. En mi código, la rama izquierda es siempre la que está a la izquierda en el constructor de datos.
  • Usaste i < fst pairy i == fst pairen guardias separados. Al hacer coincidir mayúsculas y minúsculas en la salida de compare, solo tiene que hacer la comparación una vez en lugar de dos.
  • Estabas en el camino correcto al necesitar una precisefunción, pero mucha de la lógica que tenías en closestLessrealidad necesitaba estar en ella.

Aquí hay un caso de prueba rápido, usando el ejemplo en el sitio que vinculó:

Prelude> tree = Node 9 () (Node 4 () (Node 3 () Leaf Leaf) (Node 6 () (Node 5 () Leaf Leaf) (Node 7 () Leaf Leaf))) (Node 17 () Leaf (Node 22 () (Node 20 () Leaf Leaf) Leaf))
Prelude> closestLess 4 tree
Just (4,())
Prelude> closestLess 18 tree
Just (17,())
Prelude> closestLess 12 tree
Just (9,())
Prelude> closestLess 2 tree
Nothing

También puede hacerlo más perezoso (ceder el exterior Justtan pronto como se encuentre un solo candidato), a expensas de ser un poco más complejo:

importar Data.Functor.Identity

datos TreeMap v = Hoja | Node Integer v (TreeMap v) (TreeMap v) derivación (Show, Read, Eq, Ord)

NearLess :: Integer -> TreeMap v -> Quizás (Integer, v)
más cercano Menos i = nada preciso
  dónde
    preciso :: Aplicativo t => t (Integer, v) -> TreeMap v -> t (Integer, v)
    Preciso más cercanoSoFar Hoja = más cercanoSoFar
    preciso más cercanoSoFar (Nodo kvlr) = caso i `comparar` k de
      LT -> preciso más cercanoSoFar l
      EQ -> puro (k, v)
      GT -> puro. runIdentity $ precisa ( Identidad (k, v)) r

Vea mi pregunta sobre esto para obtener más detalles al respecto.

Related questions

MORE COOL STUFF

La estrella de HGTV, Christina Hall, revela que tiene 'envenenamiento por mercurio y plomo' probablemente por voltear 'casas asquerosas'

La estrella de HGTV, Christina Hall, revela que tiene 'envenenamiento por mercurio y plomo' probablemente por voltear 'casas asquerosas'

La estrella de HGTV, Christina Hall, revela que le diagnosticaron envenenamiento por mercurio y plomo, probablemente debido a su trabajo como manipuladora de casas.

La estrella de 'Love Is Blind' Brennon Lemieux responde a los cargos de violencia doméstica

La estrella de 'Love Is Blind' Brennon Lemieux responde a los cargos de violencia doméstica

Recientemente salió a la luz un informe policial que acusa a la estrella de 'Love Is Blind', Brennon, de violencia doméstica. Ahora, Brennon ha respondido a los reclamos.

Wynonna Judd se dio cuenta de que ahora es la matriarca de la familia Judd en un momento festivo de pánico

Wynonna Judd se dio cuenta de que ahora es la matriarca de la familia Judd en un momento festivo de pánico

Conozca cómo Wynonna Judd se dio cuenta de que ahora es la matriarca de la familia mientras organizaba la primera celebración de Acción de Gracias desde que murió su madre, Naomi Judd.

Experto en lenguaje corporal explica los 'paralelos' entre Kate Middleton y la princesa Diana

Experto en lenguaje corporal explica los 'paralelos' entre Kate Middleton y la princesa Diana

Descubra por qué un destacado experto en lenguaje corporal cree que es fácil trazar "tales paralelismos" entre la princesa Kate Middleton y la princesa Diana.

Los láseres arrojan luz sobre por qué necesita cerrar la tapa antes de descargar

Los láseres arrojan luz sobre por qué necesita cerrar la tapa antes de descargar

Los inodoros arrojan columnas de aerosol invisibles con cada descarga. ¿Como sabemos? La prueba fue capturada por láseres de alta potencia.

The Secrets of Airline Travel Quiz

The Secrets of Airline Travel Quiz

Air travel is far more than getting from point A to point B safely. How much do you know about the million little details that go into flying on airplanes?

Where in the World Are You? Take our GeoGuesser Quiz

Where in the World Are You? Take our GeoGuesser Quiz

The world is a huge place, yet some GeoGuessr players know locations in mere seconds. Are you one of GeoGuessr's gifted elite? Take our quiz to find out!

¿Caduca el repelente de insectos?

¿Caduca el repelente de insectos?

¿Sigue siendo efectivo ese lote de repelente de insectos que te quedó del verano pasado? Si es así, ¿por cuánto tiempo?

Ponle una tapa. En realidad, ponle una tapa a todo. Consigue 12 tapas de cocina elásticas de silicona por $14. [Exclusivo]

Ponle una tapa. En realidad, ponle una tapa a todo. Consigue 12 tapas de cocina elásticas de silicona por $14. [Exclusivo]

Tapas elásticas de silicona de Tomorrow's Kitchen, paquete de 12 | $14 | Amazonas | Código promocional 20OFFKINJALids son básicamente los calcetines de la cocina; siempre perdiéndose, dejando contenedores huérfanos que nunca podrán volver a cerrarse. Pero, ¿y si sus tapas pudieran estirarse y adaptarse a todos los recipientes, ollas, sartenes e incluso frutas en rodajas grandes que sobran? Nunca más tendrás que preocuparte por perder esa tapa tan específica.

Cuéntanos tus mejores trucos de Washington, DC

Cuéntanos tus mejores trucos de Washington, DC

Hemos pirateado algunas ciudades industriales en esta columna, como Los Ángeles y Las Vegas. Ahora es el momento de una ciudad militar-industrial-compleja.

Un minorista está eliminando su sección de tallas grandes y mezclando tallas más grandes con todo lo demás

Un minorista está eliminando su sección de tallas grandes y mezclando tallas más grandes con todo lo demás

Un minorista está enlatando su sección de tallas grandes. Pero no están tomando la categoría solo en línea o descontinuándola por completo.

La mejor forma de guardar animales de peluche es dentro de un puf

La mejor forma de guardar animales de peluche es dentro de un puf

Entiendo totalmente, completamente si tienes una relación difícil con los animales de peluche. Son lindos, tienen valor sentimental y es difícil separarse de ellos.

Patinaje artístico de EE. UU. 'frustrado' por falta de decisión final en evento por equipos, pide una decisión justa

Patinaje artístico de EE. UU. 'frustrado' por falta de decisión final en evento por equipos, pide una decisión justa

El equipo está a la espera de las medallas que ganó en los Juegos Olímpicos de Invierno de 2022 en Beijing, ya que se está resolviendo un caso de dopaje que involucra a la patinadora artística rusa Kamila Valieva.

Los compradores de Amazon dicen que duermen 'como un bebé mimado' gracias a estas fundas de almohada de seda que cuestan tan solo $ 10

Los compradores de Amazon dicen que duermen 'como un bebé mimado' gracias a estas fundas de almohada de seda que cuestan tan solo $ 10

Miles de compradores de Amazon recomiendan la funda de almohada de seda Mulberry, y está a la venta en este momento. La funda de almohada de seda viene en varios colores y ayuda a mantener el cabello suave y la piel clara. Compre las fundas de almohada de seda mientras tienen hasta un 46 por ciento de descuento en Amazon

Se busca al corredor de los Bengals Joe Mixon por orden de arresto emitida por presuntamente apuntar con un arma de fuego a una mujer

Se busca al corredor de los Bengals Joe Mixon por orden de arresto emitida por presuntamente apuntar con un arma de fuego a una mujer

El jueves se presentó una denuncia de delito menor amenazante agravado contra Joe Mixon.

Profesor de la Universidad de Purdue arrestado por presuntamente traficar metanfetamina y proponer favores sexuales a mujeres

Profesor de la Universidad de Purdue arrestado por presuntamente traficar metanfetamina y proponer favores sexuales a mujeres

El Departamento de Policía de Lafayette comenzó a investigar a un profesor de la Universidad de Purdue en diciembre después de recibir varias denuncias de un "hombre sospechoso que se acercaba a una mujer".

Concept Drift: el mundo está cambiando demasiado rápido para la IA

Concept Drift: el mundo está cambiando demasiado rápido para la IA

Al igual que el mundo que nos rodea, el lenguaje siempre está cambiando. Mientras que en eras anteriores los cambios en el idioma ocurrían durante años o incluso décadas, ahora pueden ocurrir en cuestión de días o incluso horas.

India me está pateando el culo

India me está pateando el culo

Estoy de vuelta por primera vez en seis años. No puedo decirte cuánto tiempo he estado esperando esto.

Precios accesibles, nuestro aprendizaje desde la perspectiva iOS

Precios accesibles, nuestro aprendizaje desde la perspectiva iOS

Cómo mejoramos la accesibilidad de nuestro componente de precio, y cómo nos marcó el camino hacia nuevos saberes para nuestro sistema de diseño. Por Ana Calderon y Laura Sarmiento Leer esta historia en inglés.

ℝ

“And a river went out of Eden to water the garden, and from thence it was parted and became into four heads” Genesis 2:10. ? The heart is located in the middle of the thoracic cavity, pointing eastward.

Language