树的最小和最大函数
我正在尝试编写一个返回树中最小值的函数。
主要问题是我认为它并没有真正返回最小值，而不仅仅是 Leaf 的一个随机值。有人跟我说要用
minBound，但是我没有找到这个函数的资料，所以我试着自己写。有人会说我的代码中的问题在哪里，也许如何使用minBound而不是我的函数？
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
回答
minBound是由Bounded类型类定义的名称，用于提供引用类型的最小元素的通用方法。例如，
data Size = Small | Medium | Large deriving (Eq, Enum, Bounded)
然后minBound :: Size == Small和maxBound :: Size == Large。
它在这里没有任何用处。即使minTreeValue需要a有一个Bounded实例，给定树x中的最小值与树可以具有的最小值几乎没有关系，除了明显的minTreeValue x >= minBound.
您的定义针对您知道具有二分搜索属性的树进行了优化，该属性表示给定值Node a b left right，则
minTreeValue left <= a <= b <= minTreeValue right
通常，树可能不具有此属性，在这种情况下，您始终必须明确比较两个值以获得较小的值。这需要对类型进行进一步的限制：a必须有一个Ord实例。
minTreeValue (Leaf a) = a
minTreeValue (Node a b left right) = minimum [a, b, minTreeValue left, minTreeValue right]
但是，现在我们有一个问题：minTreeValue Nil没有定义。但是在递归中也没有有效的默认值。你可能会认为你可以使用minBound :: a，但是这是不正确的，因为minBound是没有任何空树的最小值，因为有没有在空树值。结果，您被迫完全避免调用minTreeValue空树。
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]
这是正确的，但不完整，因为minTreeValue Nil仍未定义。您必须避免在 上调用它Nil，即使已经避免了这种递归调用。
一个解决办法是改变的类型minTreeValue来Ord a => MultTree a -> Maybe a，这样我们就可以用Nothing一个空树的最小值。这也让我们可以轻松忽略 return 的递归调用Nothing。该catMaybes函数让我们丢弃Nothing列表中的值，然后从剩余的Just值中提取值。
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]