haskell - 如何生成随机的类型化函数

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):

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 a 的实例和 Arbitrary b 的实例我们可以使函数\a -> coarbitrary a arbitrary ，其类型为 a -> Gen b .

请记住 Gen b是 StdGen -> Size -> b 的新类型, 所以类型 a -> Gen b与 a -> StdGen -> Size -> b 同构.

我们可以简单地编写一个函数，该函数接受后一种类型的任何函数并切换参数顺序以返回类型为 StdGen -> Size -> a -> b 的函数。 .

这种重新排列的类型与 Gen (a -> b) 同构，所以瞧，我们将重新排列的函数打包成 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 -> 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) 一致，所以它真的和我上面画的一样。