Haskell - necesidad de mejorar este hallazgo, el de la función para un bst a d + 1 complejidad

Question 1

data Tree a = Empty | Node (Tree a) a (Tree a) 

naive_find :: (Ord a) => (Tree a) -> a -> Bool
naive_find Empty _ = False
naive_find (Node t1 v t2) x 
    | x == v = True 
    | x  < v = naive_find t1 x 
    | x  > v = naive_find t2 x

eso es un fragmento de mi actual bst código, od supuesto, hay otras funciones, pero yo no creo que sea necesario para la pregunta. necesito reducir el anterior 2d complejidad a d + 1, pero no siempre tengo esas comparaciones anteriores para obtener a través de la búsqueda del árbol, como mínimo? Gracias. Cualquier ayuda apreciada

Question 2

Uso compare. Es parte de Data.Ord

naive_find (Node t1 v t2) x = case compare v x of
    LT -> naive_find t1 x
    EQ -> True
    GT -> naive_find t2 x

Question 3

Usted no necesita la > comparación porque en ese punto usted ya sabe que tendrá éxito, lo que se puede usar otherwise:

data Tree a = Empty | Node (Tree a) a (Tree a) 

naive_find :: (Ord a) => Tree a -> a -> Bool
naive_find Empty _ = False
naive_find (Node t1 v t2) x 
    | x == v    = True 
    | x  < v    = naive_find t1 x 
    | otherwise = naive_find t2 x

Paul Johnson · Answer 1 · 2021-11-23T14:13:24

Uso compare. Es parte de Data.Ord

naive_find (Node t1 v t2) x = case compare v x of
    LT -> naive_find t1 x
    EQ -> True
    GT -> naive_find t2 x

Noughtmare · Answer 2 · 2021-11-23T17:20:52

Usted no necesita la > comparación porque en ese punto usted ya sabe que tendrá éxito, lo que se puede usar otherwise:

data Tree a = Empty | Node (Tree a) a (Tree a) 

naive_find :: (Ord a) => Tree a -> a -> Bool
naive_find Empty _ = False
naive_find (Node t1 v t2) x 
    | x == v    = True 
    | x  < v    = naive_find t1 x 
    | otherwise = naive_find t2 x

Haskell - necesidad de mejorar este hallazgo, el de la función para un bst a d + 1 complejidad

Pregunta

Mejor respuesta

En otros idiomas

Esta página está en otros idiomas

Popular en esta categoría

Las preguntas más habituales en esta categoría