如何生成随机的类型函数

Question

我想以编程方式生成随机Haskell函数并对其进行评估.在我看来,唯一的方法是基本上以编程方式生成Haskell代码并使用GHC API或外部进程运行它,返回一个字符串,并将其解析回Haskell数据类型.这是真的？

我的理由如下.函数是多态的,所以我不能使用Typeable.更重要的是,即使我编写自己的类型检查器并使用其类型注释每个函数,我也无法向Haskell编译器证明我的类型检查器是正确的.例如,当我从一个异构函数集中提取两个函数并将一个函数应用于另一个函数时,我需要为编译器提供一个保证,即我用来选择这些函数的函数只选择具有相应类型的函数.但是没有办法做到这一点,对吧？

Answer 1

DarkOtter的评论提到了QuickCheck Arbitrary和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 = ...

我不会写出实现,但想法是这样的:

1. 使用我们的CoArbitrary实例a和Arbitrary实例b可以创建\a -> coarbitrary a arbitrary具有类型的函数a -> Gen b.
2. 请记住,这Gen b是一个StdGen -> Size -> b新类型,因此类型a -> Gen b是同构的a -> StdGen -> Size -> b.
3. 我们可以简单地编写一个函数,该函数接受后一种类型的任何函数,并切换参数顺序以返回类型的函数StdGen -> Size -> a -> b.
4. 这种重新排列的类型是同构的Gen (a -> b),所以我们将重新排列的函数打包成a Gen,然后我们得到了随机函数发生器!

我建议你阅读QuickCheck的来源,亲自看看.当你解决这个问题时,你只会遇到两个额外的细节,可能会减慢你的速度.首先,Haskell RandomGen类有这个方法:

-- | The split operation allows one to obtain two distinct random generators.
split :: RandomGen g => g -> (g, g)

此操作在Monad实例中使用Gen,并且相当重要.这里的一个技巧是StdGen纯伪随机数发生器; Gen (a -> b)工作方式是,对于a扰动b发电机的每个可能值,使用扰动发电机产生b结果,但是我们永远不会推进扰动发电机的状态 ; 基本上生成的a -> b函数是对伪随机种子的闭包,每次a我们用它a来调用它时我们使用特定的确定性地创建一个新种子,然后用它来确定性地生成b依赖于a隐藏种子的种子.

缩写类型Seed -> a -> b或多或少地总结了正在发生的事情 - 伪随机函数是用于b从伪随机种子生成a的规则a.这不适用于命令式风格的有状态随机数生成器.

第二:不是直接使用(a -> StdGen -> Size -> b) -> StdGen -> Size -> a -> b我上面描述的函数,而是使用QuickCheck代码promote :: Monad m => m (Gen a) -> Gen (m a),这是对任何函数的概括Monad.如果m是的函数实例Monad,promote不谋而合(a -> Gen b) -> Gen (a -> b),所以我素描上面这真的一样.