gistfile1.hs

{-# LANGUAGE ScopedTypeVariables #-}

module BST where

import Test.QuickCheck
import Control.Monad
import Control.Applicative

data  BST a = Empty
           | Node {value :: a, left :: BST a, right :: BST a}
           deriving Show

isBST :: Ord a => BST a -> Bool
isBST Empty = True
isBST (Node v l r) = (checkBranch (<) l) && (checkBranch (>) r)
  where checkBranch f (Empty :: BST a) = True
        checkBranch f b@(Node v' _ _) = (f v v') && (isBST b)

instance (Arbitrary a, Ord a) => Arbitrary (BST a) where
  arbitrary = sized genBST where
    genBST n = frequency [
      (2, return Empty),
      (abs n, Node <$> arbitrary
              <*> genBST (n - 2) <*> genBST (n - 2))]

test = quickCheck isBST