生成具有具体类型的任意“JointList”

Question

我正在为 this course homework 的练习之一编写测试。

在这个作业中定义了以下数据类型：

data JoinList m a = Empty
              | Single m a
              | Append m (JoinList m a) (JoinList m a)
              deriving (Eq, Show)

为了进行测试，我想使用 QuickCheck 生成随机的 JointList 元素，这样 m 就是一个携带信息的 Monoid关于列表中元素的数量。也就是说，我想定义 arbitrary 如下：

instance (Sized m0, Monoid m0, Arbitrary a0) => 
    (Arbitrary (JoinList m0 a0)) where
  arbitrary = oneof [ return Empty
                    , liftM (Single (Size 1)) arbitrary
                    , liftM2 (doAppend) arbitrary arbitrary
                    ]
              where doAppend jxs jys = Append (tag jxs <> tag jys) jxs jys

其中<>定义为两个操作数大小之和，Sizedclass定义如下：

newtype Size = Size Int
    deriving (Eq, Ord, Show, Num)

class Sized a where
  size :: a -> Size

但是，这会导致以下编译器错误：

Couldn't match expected type ‘m0’ with actual type ‘Size’
  ‘m0’ is a rigid type variable bound by
       the instance declaration at test/Spec.hs:35:10
Relevant bindings include
  arbitrary :: Gen (JoinList m0 a0) (bound at test/Spec.hs:36:3)
In the first argument of ‘Single’, namely ‘(Size 1)’
In the first argument of ‘liftM’, namely ‘(Single (Size 1))’

有办法实现吗？

Answer 1

我怀疑您不是支持生成由用户选择的 Sized 实例注释的随机列表，而是真的只想支持生成由特定类型 Size 注释的随机列表。您可以通过这种方式修改 Arbitrary 实例声明：

instance (m ~ Size, Arbitrary a) => Arbitrary (JoinList m a) where
    -- as before

您需要为 Size 声明明显的 Monoid 实例：

instance Monoid Size where
    mempty  = 0
    mappend = (+)

您可以完全跳过 Sized class 的声明。

或者，如果您确实打算生成由用户选择的实例注释的随机列表，那么您需要 Sized class 提供一种方法来生成注释，而不是像 class 当前提供的那样使用它们。因此，例如：

class Sized a where size :: Int -> a
instance Sized Size where size = Size

然后 Arbitrary 实例声明将保持不变，但会在 Single.

的生产中将 Size 替换为 size

生成具有具体类型的任意“JointList”

Generating arbitrary `JointList` with concrete types

haskell

quickcheck