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

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.

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.