¿Cómo puedo verificar si una BST es válida?

Question

¿Cómo puedo verificar si una BST es válida, dada su definición y el uso de una versión generalizada de fold para BST?

data(Ord a, Show a, Read a) => BST a = Void | Node { 
    val :: a, 
    left, right :: BST a 
} deriving (Eq, Ord, Read, Show) 


fold :: (Read a, Show a, Ord a) => (a -> b -> b -> b) -> b -> BST a -> b 
fold _ z Void   = z 
fold f z (Node x l r) = f x (fold f z l) (fold f z r) 

La idea es comprobar que un valor de nodo es mayor que todos los valores de izquierda-subárbol y más pequeño que todos los valores en su derecho-subárbol. Debe ser True para todos los nodos en el árbol. Una función bstList simplemente muestra la lista de valores (ordenados) en BST.

Por supuesto algo como esto no funcionará:

--isBST :: (Read a, Show a, Ord a) => BST a -> Bool 
isBST t = fold (\x l r -> all (<x) (bstList l) && all (>x) (bstList r)) (True) t 

porque, por ejemplo, la aplicación de la función de plegado al nodo 19 termina all (<19) (bstList True) && all (>19) (bstList True).

Answer 1

Su problema parece ser que se pierde información debido a que su función sólo devuelve un valor lógico cuando se examina la subárboles izquierdo y derecho. Entonces cámbialo para devolver también los valores mínimos y máximos de los subárboles. (Esto es probablemente más eficiente también, ya que no necesita usar bslist para verificar todos los elementos)

Y haga una función de envoltura para ignorar estos valores "auxiliares" una vez que haya terminado, por supuesto.

Answer 2

(Por favor no ponga clase de tipos limitaciones en el tipo data.)

Un BST es válida si y sólo si una en orden transversal está aumentando de forma monótona.

flatten tree = fold (\a l r -> l . (a:) . r) id tree [] 

ordered list@(_:rest) = and $ zipWith (<) list rest 
ordered _ = True 

isBST = ordered . flatten 

Answer 3

Si no insiste en usar un pliegue puede hacerlo de esta manera:

ord Void = True 
ord (Node v l r) = every (< v) l && every (> v) r && ord l && ord r where 
    every p Void = True 
    every p (Node v l r) = p v && every p l && every p r 

Answer 4

Una buena manera de codificar esto es para apoyarse en el recorrido proporcionada por Data.Foldable.

{-# LANGUAGE DeriveFunctor, DeriveFoldable #-} 
import Data.Foldable 
import Data.Monoid 

Podemos obtener una instancia del mismo de forma automática utilizando una extensión, pero tenemos que cambiar el orden de los campos del nodo constructor para proporcionar un recorrido en orden.

Mientras estamos en ello, debemos eliminar las limitaciones en el tipo de datos en sí. Que en realidad no proporcionan ningún beneficio, y se ha quitado de la lengua como de Haskell 2011. (Cuando se desea utilizar este tipo de limitaciones que debe ponerlos en instancias de clases, no en el tipo de datos.)

data BST a 
    = Void 
    | Node 
    { left :: BST a 
    , val :: a 
    , right :: BST a 
    } deriving (Eq, Ord, Read, Show, Foldable) 

Primera definimos lo que significa que una lista esté estrictamente ordenada.

sorted :: Ord a => [a] -> Bool 
sorted [] = True 
sorted [x] = True 
sorted (x:xs) = x < head xs && sorted xs 
-- head is safe because of the preceeding match. 

entonces podemos utilizar el método toList proporcionada por Data.Foldable y el ayudante anteriormente.

isBST :: Ord a => BST a -> Bool 
isBST = sorted . toList 

También podemos implementar esto más directamente, como usted pidió. Como eliminamos las restricciones espurias en el tipo de datos, podemos simplificar la definición de su doblez.

cata :: (b -> a -> b -> b) -> b -> BST a -> b 
cata _ z Void   = z 
cata f z (Node l x r) = f (cata f z l) x (cata f z r) 

Ahora necesitamos un tipo de datos para modelar el resultado de nuestra catamorphism, que es que o bien no tienen nodos (Z), o un rango de estrictamente creciente nodos (T) o han fallado (X)

data T a = Z | T a a | X deriving Eq 

Y entonces podemos aplicar directamente isBST

isBST' :: Ord a => BST a -> Bool 
isBST' b = cata phi Z b /= X where 
    phi X _ _ = X 
    phi _ _ X = X 
    phi Z a Z = T a a 
    phi Z a (T b c) = if a < b then T a c else X 
    phi (T a b) c Z = if b < c then T a c else X 
    phi (T a b) c (T d e) = if b < c && c < d then T a e else X 

Esto es un poco tedioso, por lo perha ps sería mejor para descomponer la forma en que componemos los estados intermedios un poco:

cons :: Ord a => a -> T a -> T a 
cons _ X = X 
cons a Z = T a a 
cons a (T b c) = if a < b then T a c else X 

instance Ord a => Monoid (T a) where 
    mempty = Z 
    Z `mappend` a = a 
    a `mappend` Z = a 
    X `mappend` _ = X 
    _ `mappend` X = X 
    T a b `mappend` T c d = if b < c then T a d else X 

isBST'' :: Ord a => BST a -> Bool 
isBST'' b = cata phi Z b /= X where 
    phi l a r = l `mappend` cons a r 

En lo personal, yo probablemente sólo tiene que utilizar la instancia plegable.