CODEWITHSUNDEEP
haskellpattern-matchingbinary-search-treebinary-search
AJ.beProgramming
AJ.beProgramming

Reputation: 87

Haskell Binarysearchtree, checker function problem

I would like to write a function in haskell, which checks if a Binarytree with this specific structure:

data BB a = L | K a (BB a) (BB a) deriving Show

is a BinarySearchTree or not. An example for a BinarySearchTree:

baumA = K 5 (K 3 (K 1 L L) L) (K 7 L (K 12 (K 9 L L) L))

The function I wrote works, but gives me some warnings im unclear of why they're appearing. The warnings are:

"Pattern match has inaccessible right hand side In an equation for `hilf': hilf (K w L L) acc 0 = ..."

and

"Pattern match is redundant In an equation for `hilf': hilf (K w L L) acc 1 = ..."

The code for my funciton is this here:

isBinarySearchTree :: Ord a => BB a -> Bool
isBinarySearchTree (K initial l r) = hilf l initial 0 && hilf r initial 1 
-- "0" means left side and "1" means right side


hilf L _ _ = True -- neutral case

hilf (K w l r) acc 0                                
    | w < acc && hilf l w 0 && hilf r w 1 = True
    | otherwise = False

hilf (K w L L) acc 0
    | w < acc  = True
    | otherwise = False

hilf (K w l r) acc 1
    | w > acc && hilf l w 0 && hilf r w 1 = True
    | otherwise = False

hilf (K w L L) acc 1
    | w > acc  = True
    | otherwise = False

Upvotes: 1

Views: 175

Answers (1)

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 476574

Your hilf will never visit hilf (K w L L) acc 0, since hilf (K w l r) acc 0 matches even if l and r are (both) L. The patterns for hilf (K w L L) acc 0 and hilf (K w L L) acc 1 this will never be visited.

But even if that is the case the checker will not work: a node is not a lift or a right one. Most nodes are inner nodes, and thus have to satisfy two constraints: the value should be less than a given value and more than a certain value.

You can work with a helper function that has two Maybe as as constraints. If it is a Nothing that means that the constraint is "not active", whereas Just x means that the value should be greater (or smaller) than a given value. We thus can make two helper functions:

checkOrd1 :: Ord a => Maybe a -> a -> Bool
checkOrd1 Nothing _ = True
checkOrd1 (Just x) y = x < y

checkOrd2 :: Ord a => a -> Maybe a -> Bool
checkOrd2 _ Nothing = True
checkOrd2 x (Just y) = x < y

checkOrd :: Ord a => Maybe a -> a -> Maybe a -> Bool
checkOrd l x g = checkOrd1 l x && checkOrd2 x g

then our isBinarySearchTree calls the helper function with at that moment two disabled constraints:

isBinarySearchTree :: Ord a => BB a -> Bool
isBinarySearchTree tree = hilf Nothing Nothing tree

The hilf for a leave L is always true, for a node K we thus split it up in two extra checks:

hilf :: Ord a => Maybe a -> Maybe a -> BB a -> Bool
hilf _ _ L = True
hilf l g (K v left right) = checkOrd l v g && hilf … left && hilf … right

where I leave filling in the … parts as an exercise. You here thus should reuse the constraints you inerhit, but use the value v as a new upperbound for the left subtree and lowerbound as the right subtree.

Upvotes: 1

Related Questions