How can I check if a BST is valid?

Question

How can I check if a BST is a valid one, given its definition and using a generalized version of fold for 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)

The idea is to check that a node value is greater then all values in left-subtree and smaller than all values in its right-subtree. This must be True for all nodes in the tree. A function bstList simply output the list of (ordered) values in the BST.

Of course something like this won't work:

--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

because, for example, applying the fold function to the node 19 ends up all (<19) (bstList True) && all (>19) (bstList True).

Answer 1

Your problem seems to be that you lose information because your function only returns a boolean when it examines the left and right subtrees. So change it to also return the minimum and maximum values of the subtrees. (This is probably more efficient as well, since you don't need to used bslist to check all elements anymore)

And make a wrapper function to ignore these "auxiliary" values after you are done, of course.

Answer 2

(Please don't put typeclass constraints on the data type.)

A BST is valid iff an in-order traversal is monotonically increasing.

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

A nice way of encoding this is to lean on the traversal provided by Data.Foldable.

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

We can derive an instance of it automatically using an extension, but we need to reorder the fields of the Node constructor to provide us an in-order traversal.

While we're at it, we should eliminate the constraints on the data type itself. They actually provide no benefit, and has been removed from the language as of Haskell 2011. (When you want to use such constraints you should put them on instances of classes, not on the data type.)

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

First we define what it means for a list to be strictly sorted.

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.

Then we can use the toList method provided by Data.Foldable and the above helper.

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

We can also implement this more directly, like you asked. Since we removed the spurious constraints on the data type, we can simplify the definition of your fold.

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)

Now we need a data type to model the result of our catamorphism, which is that we either have no nodes (Z), or a range of strictly increasing nodes (T) or have failed (X)

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

And we can then implement isBST directly

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

This is a bit tedious, so perhaps it would be better to decompose the way we compose the interim states a bit:

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

Personally, I'd probably just use the Foldable instance.

Answer 4

If you don't insist on using a fold you can do it like this:

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