I'm trying to write code that if given a tree, will go through the tree and return the minimum value in that tree, if the tree is empty, it will return val. What I have right now compiles but will not run. Any help?
minValue :: Ord a => a -> BTree a -> a
minValue val Empty = val
minValue val (BNode v left Empty) = minimum [minValue v left]
minValue val (BNode v Empty right) = minimum [minValue v right]
minValue val (BNode v left right) = minimum ([minValue v left]++[minValue v right])
I'm assuming that BTree is defined as
data BTree a = Empty | BNode a (BTree a) (BTree a) deriving (Eq, Show)
Although for future reference please include data type definitions in your question.
The key to the solution here is that the minimum of a node is the minimum of its value and the mins of each branch:
minValue :: Ord a => a -> BTree a -> a
minValue val Empty = val
minValue val (BNode v left right) =
let leftMin = minValue val left
rightMin = minValue val right
in ???
Instead of worrying if the left or right is Empty, just trust the recursion to handle it. If left is Empty, then minValue val left will just be val, and similarly for right. Then you have 4 values in scope that you want to determine the minimum of, val, v, leftMin, and rightMin. How might you do that?
minimumto do this. In the second and third equation they're superfluous anyway—the minimum of a one-element list is the list's one element.minValue 17 (BNode 22 Empty Empty) == 22Maybe areturn type may help you cope with Empty trees. Then, at a higher level, you can determine what a reasonable "default" value should be.