使用折叠操作的Haskell树

Question

给定使用折叠的定义，我将如何编写一个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函数。

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

那么，您如何做其他部分呢？

任何帮助将不胜感激。

Answer 1

在您学习时，我将通过问您更多问题来回答您的问题。

回复treeContains：

1. 您要在中计算什么值...？什么意思 它是什么类型？

   在中...，您要查找树中的下一个节点，然后检查该节点是否在您要的位置。

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

      检查您要寻找的节点是否在根目录中。如果返回true，否则检查它是否在任何子树中。如果返回true，否则检查是否有任何子子树。如果存在，则检查那些子子树中的节点，否则返回false。

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

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

   y是包含type元素的列表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. 您可以计算的...来源y吗？您需要什么功能？它/它们的类型是什么？

回复treeBalanced：

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

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

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