二叉树的最小值

Question

我正在尝试使用 foldTree 定义一个 minTree 函数定义：

foldTree :: (b -> a -> b -> b) -> b -> Tree a -> b
foldTree f e Leaf         = e
foldTree f e (Node left x right) = f (foldTree f e left) x (foldTree f e right)

这是我目前所掌握的。

minTree :: (Ord a) => Tree a -> Maybe a
minTree f e Leaf = e
minTree tree = foldTree f e tree
             where
             f x nothing  = Just x
             f x (Just y) = Just (min x y)
             e            = Nothing

但是这段代码不起作用，并给出了一些我不明白如何修复的错误。谁能帮我找出问题所在以及如何解决。

Answer 1

在你的例子中 b ~ Maybe a。因此，这意味着 f 的第一个和第三个参数是 Maybe a。因此，您将需要检查两者。第二项是 a。因此，您的 f 应该确定两个 Maybe a 和一个 a 中的最小值，例如：

minTree :: Ord a => Tree a -> Maybe a
minTree tree = foldTree f <strong>Nothing</strong> tree
    where f Nothing y Nothing = Just y
          f Nothing y (Just z) = …
          f (Just x) y Nothing = …
          f (Just x) y (Just z) = …

我将实现 … 部分作为练习。由于 a 是 Ord 类型类的成员，因此您可以使用 min :: Ord a => a -> a -> a.

二叉树的最小值

minimal value of Binary Tree

binary-tree

haskell