Haskell:返回二进制树中所有子字符串的列表。我的代码正确吗?

看起来不错。只回答一个问题:空树的所有子树列表是什么?

在我看来,测试这样的东西的最好方法是 财产 您希望您的函数能够满足的,然后编写一些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 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.

现在您可以考虑测试其他财产。