haskell - 在 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

在 Empty 构造函数的情况下，您没有 a 的合理值。 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