haskell - 树的最小和最大函数

Question

我正在尝试编写一个返回树中最小值的函数。

主要问题是我不认为它真的返回最小值，而不仅仅是 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  

Answer 1

minBound 是由 Bounded 类型类定义的名称，用于提供引用类型的最小元素的通用方式。例如，

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

然后 minBound::Size == Small 和 maxBound::Size == Large。

---

它在这里没有任何用处。即使 minTreeValue 要求 a 有一个 Bounded 实例，给定树 x 中的最小值也没有什么关系除了明显的 minTreeValue x >= minBound 之外，树可以的最小值。

---

您的定义已针对您知 Prop 有二进制搜索属性的树进行了优化，该属性表示给定一个值 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 为空树的最小值。这也让我们很容易忽略返回 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]