0

给定这个使用折叠的定义，我将如何编写一个contains，平衡的函数。

data Tree a = Tree a [Tree a]

treeFold :: (a -> [b] -> b) -> Tree a -> b
treeContains :: Eq a => a -> Tree a -> Bool
treeBalanced :: Tree a -> Bool

请注意，在上面的定义中，不允许使用空树，并且叶子是具有空子树列表的树。

contains函数确定树是否包含给定的标签。

平衡函数确定树是否平衡。

一棵树是平衡的，如果它的子树的高度最多相差一个，并且子树是平衡的

到目前为止，我得到的 contains 函数如下所示。

treeContains :: Eq a => a -> Tree a -> Bool
treeContains a = treeFold (\x y -> if a == x then True else ...)

那么你如何做else部分指示...

任何帮助将不胜感激。

4

1 回答 1

5

在您学习的过程中，我将通过向您提出更多问题来回答您的问题。

回复treeContains：

  1. 您想在 中计算什么值...？这应该是什么意思？它的类型是什么？

    在 中...，您要查找树中的下一个节点并检查该节点是否是您所追求的。

    1. 下一个节点是哪个节点？如果当前节点有四个子树，为什么我们只想检查其中一个？如果没有子树怎么办？

      检查您所追求的节点是否在根目录中。如果它返回真，否则检查它是否在任何子树中。如果返回true，否则检查是否有任何子子树。如果有则检查那些子子树中的节点，否则返回false。

      1. 你是说你应该以广度优先顺序检查节点。这是检查它们的最佳顺序吗？您还可以查看哪些其他订单？他们会更容易吗？

  2. 是什么y意思？它的类型是什么？

    y是包含类型元素的列表b。

    1. 你可以说得更详细点吗？（我问的是 的具体情况treeContains，而不是更一般的情况treeFold。） 什么是b？

      y是一个包含类型元素的列表Tree a（b也是Tree a）

      你确定吗？

      1. 有人告诉你treeContains :: Eq a => a -> Tree a -> Bool，那是什么类型的treeContains a？

      2. 你已经决定了treeContains a = treeFold (\x y -> if a == x then True else ...)。鉴于此以及您对上一个问题的回答， 的类型是treeFold (\x y -> if a == x then True else ...)什么？

      3. 鉴于您对上一个问题的回答，并且鉴于 ， treeFold :: (a -> [b] -> b) -> Tree a -> b的类型是 (\x y -> if a == x then True else ...)什么？

      4. 鉴于您对上一个问题的回答， 的类型是y什么？

    2. 这个值是什么意思？它是否告诉您有关树中其他节点的信息？整个子树？哪个？它告诉你关于他们的什么？他们的大小？他们的身高？它们是否平衡？关于他们的内容？

  3. 你能计算出...fromy吗？您需要什么功能？它/他们的类型是什么？

回复treeBalanced：

  1. 如果你想写一个函数treeHeight :: Tree a -> Int，你会怎么做？你会用treeFold吗？

  2. 如果你想写一个函数treeHeightAndBalanced :: Tree a -> (Int, Bool)，你会怎么做？

  3. 如果你已经有了treeHeightAndBalanced :: Tree a -> (Int, Bool)，你怎么写treeBalanced :: Tree a -> Bool？

于 2013-04-26T10:41:23.130 回答