1

我想使用 SmallCheck 来测试我的代码。我设法生成了任意的整数对列表，但这不是我的类型应该包含的内容。该列表表示一组范围，其中[1,3),[4,6)将被编码/存储为[(1,3),(4,6)].

这些是我的范围的标准化形式的不变量：

fst a < snd a 
snd a < fst b where a is before b in the list

我想将此传达给 SmallCheck，以便它不会生成大量我丢弃的值，因为它们不满足我的不变量，但也许这是不可能的。

如何生成满足我的不变量的列表？

4

2 回答 2

3

优先使用特定于应用程序的类型而不是内置的 int 类型（Int、List）。这不仅适用于 SmallCheck，而且适用于任何语言的任何软件。

data Interval = Interval (Int,Int)
data Domain = Domain [Interval]

编写强制执行不变量的智能构造函数。

interval :: Int -> Int -> Interval
interval x y = Interval (min x y, max x y) -- if you want this

domain :: [Interval] -> Domain
domain ints = Domain ... (something that sorts intervals, and perhaps merges them)

然后使用这些来创建串行实例。

于 2016-04-05T17:51:10.897 回答
0

我确实同意使用用户定义的类型可以更好地解决这个问题。

我假设您正在编写一个算法，该算法具有按升序排序的不相交半开区间的某些属性，那么以下提供了Serial实例。

我决定给出Interval不同AscDisjIntervals的生成器，而不是根据另一个来实现。

算法AscDisjIntervals就像我已经在评论中写的那样

  • 生成非负Integers 列表（这是为了避免Int溢出）
  • 对这些整数求和（这会断言所有值的升序
  • 从此列表生成对（如果列表具有奇数个元素，则丢弃最后一个元素）

Intervals.hs

{-# LANGUAGE FlexibleInstances, MultiParamTypeClasses #-}
module Intervals where

newtype Interval = I (Integer,Integer) deriving(Eq)

instance Show Interval where
    show (I (a,b)) = "["++show a ++ ", "++ show b ++ "]"

instance Monad m => Serial m Interval where
    series = let a_b a b = I (getNonNegative $ min a b , getNonNegative $ max a b) 
             in cons2 a_b

newtype AscDisjIntervals = ADI [Interval] deriving (Eq)

instance Show AscDisjIntervals where
    show (ADI x) = "|- "++ (unwords $ map show x) ++ " ->"

instance Monad m => Serial m AscDisjIntervals where
    series = cons1 aux1

aux1 :: [NonNegative Int] -> AscDisjIntervals
aux1 xx = ADI . generator . tail $ scanl (+) 0 xx
  where generator [] = []
        generator (_:[]) = []
        generator (x:y:xs) = let i = I (getNonNegative x ,getNonNegative y)
                        in i:generator xs

注意：我只编译了程序，没有测试任何属性。

于 2016-04-05T21:24:00.107 回答