DarkOtter 的评论提到了 QuickCheckArbitrary
和CoArbitrary
类,这当然是您应该尝试的第一件事。QuickCheck 有这个实例:
instance (CoArbitrary a, Arbitrary b) => Arbitrary (a -> b) where ...
碰巧的是,我昨天刚刚阅读了 QuickCheck 代码以了解它是如何工作的,所以我可以分享我所学到的知识,而我的脑海中还很新鲜。QuickCheck 是围绕一个看起来像这样的类型构建的(这不会完全相同):
type Size = Int
-- | A generator for random values of type @a@.
newtype Gen a =
MkGen { -- | Generate a random @a@ using the given randomness source and
-- size.
unGen :: StdGen -> Size -> a
}
class Arbitrary a where
arbitrary :: a -> Gen a
第一个技巧是 QuickCheck 有一个像这样工作的函数(我没有弄清楚它是如何实现的):
-- | Use the given 'Int' to \"perturb\" the generator, i.e., to make a new
-- generator that produces different pseudorandom results than the original.
variant :: Int -> Gen a -> Gen a
然后他们用它来实现这个CoArbitrary
类的各种实例:
class CoArbitrary a where
-- | Use the given `a` to perturb some generator.
coarbitrary :: a -> Gen b -> Gen b
-- Example instance: we just treat each 'Bool' value as an 'Int' to perturb with.
instance CoArbitrary Bool where
coarbitrary False = variant 0
coarbitrary True = variant 1
现在有了这些部分,我们想要这个:
instance (Coarbitrary a, Arbitrary b) => Arbitrary (a -> b) where
arbitrary = ...
我不会写出实现,但想法是这样的:
- 使用
CoArbitrary
instance ofa
和Arbitrary
instance ofb
我们可以创建\a -> coarbitrary a arbitrary
具有 type的函数a -> Gen b
。
- 请记住,它
Gen b
是 的StdGen -> Size -> b
新类型,因此该类型a -> Gen b
与 同构a -> StdGen -> Size -> b
。
- 我们可以简单地编写一个函数,它接受后一种类型的任何函数并切换参数顺序以返回一个类型为 的函数
StdGen -> Size -> a -> b
。
- 这个重新排列的类型与 同构
Gen (a -> b)
,所以瞧,我们将重新排列的函数打包到 aGen
中,我们得到了随机函数生成器!
我建议您阅读 QuickCheck 的源代码以亲自查看。当你解决这个问题时,你只会遇到两个可能会让你慢下来的额外细节。首先,HaskellRandomGen
类有这个方法:
-- | The split operation allows one to obtain two distinct random generators.
split :: RandomGen g => g -> (g, g)
该操作在 for 的Monad
实例中使用Gen
,并且相当重要。这里的技巧之一是它StdGen
是一个纯伪随机数生成器;可行的方法Gen (a -> b)
是,对于a
我们扰动b
生成器的每个可能值,使用该扰动生成器来生成b
结果,但是我们永远不会推进扰动生成器的状态;基本上生成的a -> b
函数是一个伪随机种子的闭包,每次我们用一些调用它时,a
我们使用特定a
的来确定性地创建一个新的种子,然后使用它来确定性地生成一个b
依赖于a
和隐藏的种子。
缩写类型Seed -> a -> b
或多或少总结了正在发生的事情——伪随机函数是b
从伪随机种子和a
. 这不适用于命令式的有状态随机数生成器。
(a -> StdGen -> Size -> b) -> StdGen -> Size -> a -> b
第二: QuickCheck 代码没有像我上面描述的那样直接具有函数,而是具有promote :: Monad m => m (Gen a) -> Gen (m a)
,这是对 any 的概括Monad
。m
的函数实例是什么时候Monad
,promote
与 重合(a -> Gen b) -> Gen (a -> b)
,所以真的和我上面画的一样。