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

我有一棵这样的树:

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类型的值。我能做什么 ？

最佳答案

对于a构造函数，您没有Empty的合理值。在这种情况下，类型Maybe可以精确编码您需要的内容:有意义的值或没有值。因此，以下是实现功能的惯用方式:

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

您可以使用functors, applicative functors and monads轻松将此功能与库的其他功能组合在一起。例如。:

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