Can someone tell me why this code isn't producing what I want.
data BST = MakeNode BST String BST
| Empty
add :: String -> BST -> BST
add new Empty = (MakeNode Empty new Empty)
add string tree@(MakeNode left value right)
| string > value = MakeNode left value (add string right)
| string < value = MakeNode (add string left) value right
| otherwise = tree
output
"John"
"Doug"
"Charlie"
"Alice"
listToBST :: [String] -> BST
listToBST = foldr add Empty
If we create and function which takes a BST and returns a list in sorted order, modelled after sort . nub, then your Tree is fine as quickcheck tells us. QuickCheck is very easy to use.
import Data.List
import Test.QuickCheck
data BST = MakeNode BST String BST
| Empty
deriving (Show)
add :: String -> BST -> BST
add new Empty = (MakeNode Empty new Empty)
add string tree@(MakeNode left value right)
| string > value = MakeNode left value (add string right)
| string < value = MakeNode (add string left) value right
| otherwise = tree
test = ["alice", "blup", "test", "aa"]
manual_test = inorder (foldr add Empty test) == sort (nub test)
prop_inorder = property inorder_test
where inorder_test :: [String] -> Bool
inorder_test xs = inorder (foldr add Empty xs) == sort (nub xs)
-- return sorted nodes
inorder :: BST -> [String]
inorder (Empty) = []
inorder (MakeNode l x r) = inorder l ++ (x : inorder r)
Just load ghci and then run quickCheck prop_inorder.
Other useful functions are:
reverseOrder :: BST -> [String]
reverseOrder Empty = []
reverseOrder (MakeNode l x r) = reverseOrder r ++ (x : reverseOrder r)
asList :: BST -> [String]
asList Empty = []
asList (MakeNode l x r) = x : (asList l ++ asList r)
And also think about making your tree more general by parameterizing over a:
data BST a = Empty | MakeNode (BST a) a (BST a)
You can make it than an instance of Functor, Monad, Foldable and all kind of handy typeclasses.
I tried it and it seems ok to me. It could help if you gave an example of an input that it doesn't work for.
I think the problem may be that string comparison does not work the way you expect ("123" < "7" because "1" < "7"). If I'm right, you might want to use Ints instead of Strings or even better, the class Ord of all the types that can be ordered using (<).
