haskell - haskell中树上的最大元素？

Question

给定一棵树:

data Tree a = Empty | Node a [Tree a] deriving Show

我正在尝试获取最大元素，因此我尝试过:

maxElem:: (Ord a) => Tree a -> Int
maxElem Empty = error "maxElem on empty Tree"
maxElem (Node a []) = a
maxElem (Node a x ) = maximum [ maxElem h | h<-x]

但是我收到错误，但没有找到它。

Answer 1

这里存在三个潜在问题:

1. 如果一棵树包含一个或多个Empty，则会出错。因此，Node 1 [Node 4 []，Empty，Node 2 [Node 5 []]] 将引发错误，因为树中存在 Empty，并且我们最终将在该 Empty 上调用 maxElem，而我们可以忽略 Empty 并因此返回 5；
2. 当您计算具有子节点的 Node 的最大值时，您也不考虑 a，而 a 可以是最大值还有；
3. 结果也是一个a，而不是Int。

这里实际上有两种情况: 1. Empty 树，引发错误；和 2. Node x cs 的最大值是 x 和子节点 maxElem 的最大值，忽略 空s。

所以我们可以写成:

maxElem:: Ord a => Tree a -> <b>a</b>
maxElem Empty = error "maxElem on Empty"
maxElem <b>(Node x cs)</b> = maximum <b>(x :</b> map maxElem <b>[c | c@(Node _ _) <- cs]</b>)

或者我们可以在列表理解中编写map maxElem:

maxElem:: Ord a => Tree a -> a
maxElem Empty = error "maxElem on Empty"
maxElem (Node x cs) = maximum (x : [<b>maxElem c</b> | c@(Node _ _) <- cs])

所以基本情况是相同的，但是Node x cs的情况计算以x为头的列表的最大值，并将 MaxElem 映射为尾部，但不是所有子节点，而是仅匹配 Node _ _ 模式的子节点。由于此列表至少包含一个元素 x，因此 maximum 在空列表上不会出错，并且我们只计算 maxElem Node 实例上的 code>。