在haskell中找到树的顶部(根)

Question

我有这样一棵树:

data Tree a
  = Empty
  | Leaf a
  | Node a (Tree a) (Tree a) String
  deriving (Show)

我需要一个找到树顶的函数.我写了这个:

root :: Tree a -> a
root (Leaf a) = a
root (Node a _ _ _) = a

哪个完美有效,但当我有一个空树时,我有一个错误信息.

如果我加

root Empty = Empty 

我再次出错,因为它没有返回类型的值a.我能做什么 ？

Answer 1

a在Empty构造函数的情况下,你没有明智的价值.Maybe在这种情况下,该类型完全符合您的需要:合理值或无值.因此,以下将是实现您的功能的惯用方法:

root :: Tree a -> Maybe a
root (Leaf a) = Just a
root (Node a _ _ _) = Just a
root _ = Nothing

您可以使用函子,应用函子和monad轻松地将此函数与库的其他函数组合在一起.例如:

functionOnPlainA :: a -> a
functionOnPlainA = error "implement me"

-- So simply we can lift our plain function to work on values of type `Maybe`.
-- This is a Functor example.
functionOnMaybeA :: Maybe a -> Maybe a
functionOnMaybeA = fmap functionOnPlainA

-- Because the above is so simple, it's conventional to inline it,
-- as in the following:
applyFunctionOnPlainAToResultOfRoot :: Tree a -> Maybe a
applyFunctionOnPlainAToResultOfRoot tree = fmap functionOnPlainA $ root tree

-- And here is an example of how Monads can serve us:
applyRootToMaybeTree :: Maybe (Tree a) -> Maybe a
applyRootToMaybeTree maybeTree = maybeTree >>= root