0

所以我试图在 Haskell 中实现一个函数，它接受二叉树并返回所有子树的列表，其中顺序和重复无关紧要，但所有子树必须至少存在一次。这是我的代码：

data BinTree a = Empty | Node (BinTree a) a (BinTree a) deriving (Eq,Show)

subtrees :: BinTree a -> [BinTree a]
subtrees Empty = [Empty]
subtrees (Node tL x tR) = [Node tL x tR] ++ subtrees tL ++ subtrees tR

这是我的数据集

(Node (Node (Node (Node Empty 1 Empty) 1 Empty) 3 Empty) 4 (Node Empty 2 Empty))

这是我的结果

[Node (Node (Node (Node Empty 1 Empty) 1 Empty) 3 Empty) 4 (Node Empty 2 Empty),
Node (Node (Node Empty 1 Empty) 1 Empty) 3 Empty,Node (Node Empty 1 Empty) 1 Emp
ty,Node Empty 1 Empty,Node Empty 2 Empty]

出于某种原因，我对这个实现有些怀疑，如果有任何反馈，我将不胜感激！谢谢！

4

2 回答 2

2

看起来还可以。只回答这个问题：什么是空树的所有子树的列表？

于 2013-09-02T15:56:34.343 回答
1

在我看来，测试此类事情的最佳方法是考虑您希望函数满足的属性，然后编写一些 QuickCheck 测试来尝试它们。QuickCheck 最棒的地方在于，如果它发现问题，它会尝试告诉您最简单的失败案例！那么让我们开始吧……

{-# LANGUAGE FlexibleInstances #-}

import Test.QuickCheck
import Control.Applicative

什么是好的属性来测试？好吧，如果我们有两棵树，t1 和 t2，并将它们与一个新节点组合起来，那么调用subtree组合树应该会给我们一个包含subtree t1, subtree t2, 以及整个树的列表。节点类型不影响逻辑，所以我选择了Char。您可能会为这个属性想一个更好的名字。

prop_combining_works :: BinTree Char -> Char -> BinTree Char -> Property
prop_combining_works t1 x t2 =
  property $ subtrees t == t : subtrees t1 ++ subtrees t2
  where t = Node t1 x t2

注意：如果不以某种方式对结果进行排序，我没想到这会起作用subtree，但幸运的是，它确实如此。但这可能会改变，这取决于您决定如何返回subtree Empty！此外，您可能需要消除 . 右侧表达式中的重复项==。

接下来，我们需要一种生成随机树进行测试的方法。下面的代码可能看起来很复杂，但它的意思是该BinTree类型的测试数据可以是Empty，也可以是Node由两个任意选择的子树和一个任意选择的Char.

instance Arbitrary (BinTree Char) where
  arbitrary = do
    oneof [return Empty, Node <$> arbitrary <*> arbitrary <*> arbitrary]

将此添加到您的代码中，然后运行 ​​QuickCheck：

λ> quickCheck prop_combining_works
Loading package QuickCheck-2.6 ... linking ... done.
+++ OK, passed 100 tests.

现在您可以考虑其他要测试的属性。

于 2013-09-02T17:26:07.117 回答