Min and Max Functions for a Tree

Question

I am trying to write a function that returns the min value in a tree.

The main problem is that I don't think that it really returns the min value and not just one random value of Leaf. Somebody said to me to use minBound, but I didn't find information for this function, so I tried to write it myself. Would someone say me where the problem in my code is, and maybe how to use minBound instead of my function?

data MultTree a = Nil | Leaf a | Node a a (MultTree a) (MultTree a) deriving Show 
minTreeValue :: MultTree a -> a
minTreeValue (Leaf a) = a
minTreeValue (Node a b Nil _) = a
minTreeValue (Node a b left _) = minTreeValue left  

Answer 1

minBound is a name defined by the Bounded typeclass, to provide a common way of referring to the smallest element of a type. For example,

data Size = Small | Medium | Large deriving (Eq, Enum, Bounded)

Then minBound :: Size == Small and maxBound :: Size == Large.

---

It doesn't serve any use here. Even if minTreeValue required a to have a Bounded instance, the smallest value in a given tree x has little relation to the smallest value the tree can have, aside from the obvious minTreeValue x >= minBound.

---

Your definition is optimized for a tree which you know has the binary search property, which says that given a value Node a b left right, then

minTreeValue left <= a <= b <= minTreeValue right

In general, the tree might not have this property, in which case you always have to explicitly compare two values to get the smaller one. This requires a further constraint on the type: a must have an Ord instance.

minTreeValue (Leaf a) = a
minTreeValue (Node a b left right) = minimum [a, b, minTreeValue left, minTreeValue right]

But, now we have a problem: minTreeValue Nil isn't defined. But there also isn't a valid default to use in the recursion. You might think you could use minBound :: a, but that would be incorrect, because minBound is not the smallest value in any empty tree, as there are no values in an empty tree. As a result, you are forced to avoid calling minTreeValue on the empty tree at all.

minTreeValue :: Ord a => MultTree a -> a
minTreeValue (Leaf a) = a
minTreeValue (Node a b Nil Nil) = minimum [a, b]
minTreeValue (Node a b left Nil) = minimum [a, b, minTreeValue left]
minTreeValue (Node a b Nil right) = minimum [a, b, minTreeValue right]
minTreeValue (Node a b left right) = minimum [a, b, minTreeValue left, minTreeValue Right]

This is correct, but partial, as minTreeValue Nil is still undefined. You have to avoid calling it on Nil, even if such recursive calls have been avoided.

One solution is to change the type of minTreeValue to Ord a => MultTree a -> Maybe a, so that we can use Nothing for the smallest value of an empty tree. This also lets us easily ignore recursive calls that return Nothing. The catMaybes function lets us discard Nothing values from a list, then extract the values from the remaining Just values.

import Data.Maybe

minTreeValue :: Ord a => MultTree a -> Maybe a
minTreeValue Nil = Nothing
minTreeValue (Leaf a) = Just a
minTreeValue (Node a b left right) = Just (minimum candidates)
  where candidates = a : b : catMaybes [minTreeValue left, minTreeValue right]