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. 如果树包含一个或多个Emptys,则会出错.所以a Node 1 [Node 4 [], Empty, Node 2 [Node 5 []]],会因为Empty树中有一个错误而引发错误,我们最终会调用maxElem它,Empty而我们可以忽略它Empty然后返回5;
2. a当你计算一个Node有孩子的最大值时你也没有考虑到,而且a也可以是最大值;
3. 结果也是一个a,而不是本身Int.

实际上有两种情况:1.Empty树,引起错误; 2. a Node x cs的最大值是孩子的最大值x和最大值maxElem,忽略Emptys.

所以我们可以把它写成:

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

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

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

所以基本情况是相同的,但是Node x cs计算maximum列表的情况是x作为头部和map MaxElem尾部,但不是所有子项,而是仅计算与Node _ _模式匹配的子项.由于此列表包含至少一个元素x,maximum因此不能在空列表上出错,并且我们仅maxElem在Node实例上计算.