5

所以我有一棵树定义为

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

我知道我可以将 Leaf 定义为 Leaf a。但我真的只是希望我的节点具有价值。我的问题是，当我进行搜索时，我有一个类型的返回值函数

Tree a -> a

由于叶子没有价值，我很困惑如果遇到叶子什么也不做。我试过了nil，，，，似乎没有任何效果。" "' '[]

编辑代码

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


breadthFirst   :: Tree a -> [a]
breadthFirst x =  _breadthFirst [x]

_breadthFirst    :: [Tree a] -> [a]
_breadthFirst [] =  []
_breadthFirst xs =  map treeValue xs ++
                _breadthFirst (concat (map immediateChildren xs))

immediateChildren                       :: Tree a -> [Tree a]
immediateChildren (Leaf)              =  []
immediateChildren (Node n left right) =  [left, right]

treeValue                         :: Tree a -> a
treeValue (Leaf)                =  //this is where i need nil
treeValue (Node n left right)   =  n

test = breadthFirst (Node 1 (Node 2 (Node 4 Leaf Leaf) Leaf) (Node 3 Leaf (Node 5 Leaf Leaf)))

main =
  do putStrLn $ show $ test
4

4 回答 4

12

在 Haskell 中，类型默认没有“空”或nil值。Integer例如，当你有 type 的东西时，你总是有一个实际的数字，而不是像nil,null或的东西None。

大多数时候，这种行为是好的。当你不期望它们时，你永远不会遇到空指针异常，因为当你不期望它们时，你永远不会有空值。然而，有时我们确实需要某种Nothing价值。您的树函数是一个完美的例子：如果我们在树中找不到结果，我们必须以某种方式表示它。

像这样添加“null”值的最明显方法是将其包装在一个类型中：

data Nullable a = Null | NotNull a

因此，如果您想要一个Integerwhich 也可以是Null，您只需使用Nullable Integer. 您可以自己轻松添加此类型；没什么特别的。

令人高兴的是，Haskell 标准库已经有了这样的类型，只是名称不同：

data Maybe a = Nothing | Just a

您可以在树函数中使用此类型，如下所示：

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

Maybe您可以通过模式匹配使用包装在 a 中的值。因此，如果您有一个列表[Maybe a]并且想要[String]退出，您可以这样做：

showMaybe (Just a) = show a
showMaybe Nothing  = ""

myList = map showMaybe listOfMaybes

Data.Maybe最后，模块中定义了一堆有用的函数。例如，mapMaybe它映射一个列表并抛出所有Nothing值。例如，这可能是您想要用于您的_breadthFirst功能的内容。

于 2013-05-10T18:17:32.400 回答
8

所以我在这种情况下的解决方案是使用Maybeand mapMaybe。简而言之，您将更treeValue改为

treeValue                         :: Tree a -> Maybe a
treeValue (Leaf)                =  Nothing
treeValue (Node n left right)   =  Just n

然后不要使用map来组合它，而是使用mapMaybe（来自Data.Maybe），它会自动剥离Just并忽略它，如果它是Nothing.

 mapMaybe treeValue xs

瞧！

Maybe是 Haskell 的说法“某些东西可能没有价值”，它的定义如下：

data Maybe a = Just a | Nothing

这是拥有 Nullable 类型的道德等价物。Haskell 只是让您承认您必须处理它为“null”的情况。当你需要它们时，Data.Maybe有很多有用的功能，比如mapMaybe可用的。

于 2013-05-10T18:15:54.013 回答
7

在这种情况下，您可以简单地使用列表推导来代替map并摆脱treeValue：

_breadthFirst xs = [n | Node n _ _ <- xs] ++ ...

这是有效的，因为在列表推导的左侧使用模式会<-跳过与模式不匹配的项目。

于 2013-05-10T18:25:27.270 回答
3

这个函数treeValue :: Tree a -> a不能是一个总函数，因为并不是所有Tree a的值实际上都包含一个a供你返回的！ALeaf类似于空列表[]，它仍然是类型[a]，但实际上不包含 a a。

标准库中的head函数具有 type [a] -> a，它也不能一直工作：

*Main> head []
*** Exception: Prelude.head: empty list

您可以编写treeValue类似的行为：

treeValue :: Tree a -> a
treeValue Leaf = error "empty tree"
treeValue (Node n _ _) = n

但这实际上对您没有帮助，因为如果任何 is 值，现在都会map treeValue xs抛出错误。xsLeaf

head出于这个原因，有经验的 Haskeller 通常会尽量避免使用类似的功能。当然，没有办法a从任何给定的[a]or中得到 a Tree a，但也许你不需要这样做。在您的情况下，您实际上是在尝试从列表中获取列表，并且您很高兴简单地对列表没有任何贡献而不是抛出错误。但不能帮助你建立它。这是帮助您解决问题的错误功能。aTreeLeaftreeValue :: Tree a -> a

Tree a -> Maybe a正如在其他一些答案中很好地解释的那样，一个可以帮助您做任何您需要的功能的功能。这使您可以稍后决定如何处理“缺失”值。当你去使用 时Maybe a，如果真的没有别的事可做，你可以调用errorthen （或使用fromJustwhich 正是这样做的），或者你可以决定还要做什么。但是 atreeValue声称能够a从 any返回 anTree a然后error在它不能拒绝任何调用者决定在没有的情况下做什么时调用a。

于 2013-05-11T01:28:56.383 回答