Haskell 快速检查生成和测试玫瑰树？

Question

我正在尝试一个简单的玫瑰树代码。

data RoseT a = Leaf a | Node a [RoseT a] deriving (Show)

instance Eq (RoseT a) where
 (==) (Leaf a) (Leaf b) = a == b
 (==) (Node a rs1) (Node b rs2) = and ((a==b): (zipWith (==) rs1 rs2))
 (==) _ _ = False 

我可以使用quickcheck来测试Eq实例的实现吗？如果是，怎么办？如果不是，最好的选择是什么？

我还有一个执行以下操作的函数:

appendPath :: (RoseT a) -> (RoseT (a,[a]))
appendPath rst = appendPath' [] rst 

appendPath :: [a] -> (RoseT a) -> (RoseT (a,[a]))
appendPath' p (Leaf a) = Leaf (a,p)
appendPath' p (Node a rs) = Node (a,p) (map (appendPath' (a:p)) rs)

函数appendPath将一棵玫瑰树作为输入，并返回一棵玫瑰树，该树的每个节点都有从节点到根的路径。我在另一个函数中使用了此信息。

如何使用 Quickcheck 在大型玫瑰树上检查此实现？

编辑:正如 mhwombat 所建议的，编写将类型参数作为参数的生成器似乎是不可能的。这是我的类型参数。我想构造一个代表有效随机算术表达式的字符串 RoseT，其中算术表达式本身遵循以下结构:

数据表达式 = Var String |添加表达式 [表达式] | MulExpr [Expr] 导出 Show

那么，有没有一种方法可以生成随机 RoseT Expr，其中 Expr 本身是仅使用快速检查随机生成的？

再次感谢 mhwombat，谢谢你对我婴儿步的包容。

Answer 1

除非我遗漏了某些内容，否则您的 RoseT 的 Eq 实现与默认的派生实现相同。所以你可以说

data RoseT a = Leaf a | Node a [RoseT a] deriving (Show, Eq)

并且忘记实例Eq(RoseT a)在哪里东西。

下一个问题是这是否能满足您的测试需求。如果您使用浮点类型参数(例如 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 -- stub

我们可以对生成的测试数据进行采样，如下所示:

λ> 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 -- changed this to keep complexity in bounds
  return $ Leaf c
sizedArbTestRoseT n = do
  c <- sizedArbExpr (n-1) -- changed this to keep complexity in bounds
  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)，这似乎有点不寻常。换句话说，你正在创造树中的树。当然，我不知道你的应用程序。