除非我漏掉了什么,你对
RoseT
的
Eq
实现与默认派生实现相同。因此,你可以直接这样说:
data RoseT a = Leaf a | Node a [RoseT a] deriving (Show, Eq)
并且忘记 instance Eq (RoseT a) where
的内容。
下一个问题是这是否能满足您的测试需求。如果您正在使用浮点类型参数进行测试,例如 RoseT Double
,那么您需要考虑由于舍入而产生的差异。在这种情况下,您需要一个比较两个树的函数,并查看值是否“足够接近”。
但是,我怀疑您的 RoseT
实现不会以任何方式依赖于类型参数。在这种情况下,您可以使用简单的类型(如 Char
或 Int
)对其进行测试,并使用 ==
进行任何所需的比较。
您有两个 appendPath
的类型签名。我认为第二个应该是 appendPath'
:
appendPath' :: [a] -> (RoseT a) -> (RoseT (a,[a]))
现在来讲如何进行测试。最好你/QuickCheck能够对被测试的树的复杂度进行一定的控制。这样做有助于你,因为最简单的树将首先进行测试,因此你可以“早期”发现错误(即使用更简单的测试用例进行调试)。你可以通过实现一个适用于你的类的“大小”生成器来实现这一点。以下是一种方法。 "size" 参数的值越高,树具有的层数就越多。
type TestRoseT = RoseT Char
sizedArbTestRoseT :: Int -> Gen TestRoseT
sizedArbTestRoseT 0 = do
c <- arbitrary
return $ Leaf c
sizedArbTestRoseT n = do
c <- arbitrary
subtreeCount <- choose (0,n-1)
subtrees <- vectorOf subtreeCount (sizedArbTestRoseT (n-1))
return $ Node c subtrees
instance Arbitrary TestRoseT where
arbitrary = sized sizedArbTestRoseT
prop_appendPath_does_something :: TestRoseT -> Property
prop_appendPath_does_something t = undefined
我们可以这样对生成的测试数据进行抽样:
λ> sample (sizedArbTestRoseT 2)
Node '\a' [Node '\RS' []]
Node '?' []
Node '\158' []
Node 'o' [Node 'E' []]
Node '\196' []
Node '4' [Node 'G' []]
Node ';' [Node 'f' []]
Node 'A' [Node '\CAN' []]
Node '!' []
Node 'q' [Node '\t' []]
Node '\'' [Node '\212' []]
编辑:
对于您的Expr
类型,我们可以编写以下生成器:
sizedArbExpr :: Int -> Gen Expr
sizedArbExpr 0 = do
s <- arbitrary
return $ Var s
sizedArbExpr n = do
es <- vectorOf 2 (sizedArbExpr (n-1))
elements [AddExpr es, MulExpr es]
instance Arbitrary Expr where
arbitrary = sized sizedArbExpr
我们需要修改
TestRoseT
及其生成器,以使树的复杂度与“size”参数一致。
type TestRoseT = RoseT Expr
sizedArbTestRoseT :: Int -> Gen TestRoseT
sizedArbTestRoseT 0 = do
c <- sizedArbExpr 0
return $ Leaf c
sizedArbTestRoseT n = do
c <- sizedArbExpr (n-1)
subtreeCount <- choose (0,n-1)
subtrees <- vectorOf subtreeCount (sizedArbTestRoseT (n-1))
return $ Node c subtrees
测试这些修改后,会得到类似以下的结果:
λ> sample (sizedArbTestRoseT 3)
Node (MulExpr [MulExpr [Var "",Var ""],AddExpr [Var "",Var ""]]) [Node (MulExpr [Var "",Var ""]) [Node (Var "") []]]
Node (MulExpr [AddExpr [Var "",Var ""],AddExpr [Var "",Var ""]]) [Node (AddExpr [Var "",Var ""]) []]
Node (MulExpr [AddExpr [Var "\164D",Var "\151\246\FS"],MulExpr [Var ":\149j\EM",Var "h\253\255"]]) [Node (MulExpr [Var "\CAN\a\ACK",Var "\184"]) [Node (Var "t\154]\\") []],Node (MulExpr [Var "\135",Var "\f\DEL\\"]) [Node (Var "\SOH\DEL") []]]
Node (AddExpr [AddExpr [Var "",Var ""],MulExpr [Var "Kj\STXV",Var "D\141<s\187"]]) []
Node (AddExpr [MulExpr [Var "\252",Var "`"],MulExpr [Var "\167`t\196",Var ":\135\NULdr\237\167"]]) []
Node (AddExpr [MulExpr [Var "]\173\&28D\SOCom",Var "^\196\ETB2\216\&2\GS\ENQ\ENQ"],AddExpr [Var "$bB\212\SOH\146\234",Var "\DC3\213\&3\SUB\\}^\246(\200"]]) [Node (MulExpr [Var "l;\133\EM\147#\SUBN\\\t",Var "\235\151U\129m3|"]) [Node (Var "\NULb\133") []],Node (AddExpr [Var "\187\EOT\165S\207\r\"\RS",Var "4"]) []]
Node (MulExpr [MulExpr [Var "%0eK",Var "`N**k\FS6\NAK"],MulExpr [Var "'lUL\NAKRPc\ENQR",Var "j\232+`\FS@n"]]) [Node (AddExpr [Var "H\DC1C%\DC48<\t\ETX.L",Var "\235+\v\STXX,\NAK\SUBQc="]) [Node (Var "f\254oX?w\224\195~/") []]]
Node (AddExpr [AddExpr [Var "P",Var "\148G\STX\DEL*\136(\161\159\&7"],AddExpr [Var "\218\136-",Var "9?\128\159\b\b%3t}\131qe"]]) [Node (MulExpr [Var "\198\249\&4\176\193/}\DC28",Var ")Gl0ym\GS"]) [Node (Var ")\204\226qA\175") []]]
Node (MulExpr [MulExpr [Var "\t\186r.",Var "j\ENQ\183\NUL\NAK\129:rg[\170o\157g\238"],AddExpr [Var "\218F\226\248\156\225\&1",Var "vu\SOH\138+CKW\EM\167\&1n"]]) [Node (MulExpr [Var ",\241\158={o\182\"5\t\STX\ETX\DC2\218\162",Var "\197\&1"]) [Node (Var "u?a};\238") []]]
Node (MulExpr [MulExpr [Var "*",Var "R"],AddExpr [Var "\CAN8C",Var "\232V.\172ILy\162a"]]) []
Node (MulExpr [MulExpr [Var "\SI\240NF\249-\v$",Var "K`\STX\231w{"],MulExpr [Var "\DC1\255\209",Var "/\227\146\236\STX\185T3r\f"]]) [Node (MulExpr [Var "\229,\DLE\NAKwf[7P\160\DEL",Var "\134#\RS\SI0KCg\195\NAK\"\191\&6\243\193\SI"]) [Node (Var "\226\&7b8\f\EOTgF\171\GS}\189c\SUBc\ETX") []]]
顺便说一下,你说“看起来不可能编写一个以类型参数作为参数的生成器”。实际上是可以做到的,但我认为这并不是你真正想要的。另外,有点不寻常的是你想创建一棵树(
RoseT
),其中叶子包含二叉树(
Expr
)。换句话说,你正在创建树的树。当然,我不知道你的应用场景。
RoseT
定义似乎不正确。玫瑰树在其 ADT 中不应该有Leaf
模式,因为使用该定义会导致叶节点的书写方式不明确,即是Leaf 42
还是Node 42 []
。这是不明确的,因为这两个表达式应该是相等的,但它们并不相等。 - Daniel Dinnyes