生成任意范围的最小限制

Question

我想为类型为

的有序树状结构生成任意值

data Tree a = Leaf | Node (Tree a) a (Tree a)

将值插入此树并同时保持其有序的函数要求该值应为 Ord。但是要为任意实例生成有序树，我需要生成“[low,hi]”范围内的值，而 Ord 不足以满足此要求。所以我还要求 value 是 Enum，因为 Enum 允许从给定边界获取值。下面的 choose 还需要 System.Random.Random:

import Test.QuickCheck.Arbitrary
import System.Random

generateTree :: (Arbitrary a, Ord a, Enum a, Random a) => a -> a -> Gen (Tree a)
generateTree l u = do
  genLeaf <- arbitrary
  if genLeaf
    then return Leaf
    else do
      x <- choose (l, u)
      left <- generateTree l (pred x)
      right <- generateTree (succ x) u
      return $ Node left x right

因此，要将其用于 arbitrary 实现，我应该在 Arbitrary class 中要求相同的 classes：

instance (Arbitrary a, Ord a, Enum a, Rand.Random a) => Arbitrary (Tree a) where
  arbitrary = do
    l <- arbitrary
    u <- arbitrary
    generateTree l u

在这里，虽然要求 Ord a => Tree a 对数据结构本身来说已经足够了，但我需要 (Arbitrary a, Ord a, Enum a, Rand.Random a) => Tree a 作为它的生成器。它看起来像是将实现细节泄漏到声明中 - 可能我看错了方式，我正在学习 Haskell。但是还是有疑问：

有没有办法声明没有那么多要求的更通用的生成器？
有没有一种方法可以为 Arbitrary (Tree a) 声明其他实例以及具有不同要求的上述实例，例如 Arbitrary (Tree Int) 仅用于 Int ？

Answer 1

因为你想要任意 ordered 树，所以没有办法摆脱 Arbitrary (Tree a) 实例中的 Ord a 约束。但是，您不需要 Enum 或 Random（回想一下 Arbitrary 正在执行随机值生成 - 因此您自然也不应该需要 Random）。

下面是我将如何实现 Arbitrary 实例。

import Test.QuickCheck.Gen
import Test.QuickCheck

arbitraryTree :: (Ord a, Arbitrary a) => Gen (Tree a)
arbitraryTree = do 
  x <- arbitrary 
  y <- suchThat arbitrary (>= x) 
  go x y 
   where 
    go mn mx = frequency [(1, return Leaf), (1, arbNode)] where

      arbNode = do 
        a <- suchThat arbitrary (\x -> x >= mn && x <= mx)
        l <- go mn a
        r <- go a mx 
        return (Node l a r) 

instance (Ord a, Arbitrary a) => Arbitrary (Tree a) where 
  arbitrary = arbitraryTree

请注意，您可以通过使用 suchThatMaybe 并提供默认值来提高可靠性，如果在一定数量的尝试中找不到范围内的合适值。

关于你的第二个问题，你确实可以有以下几种情况：

{-# LANGUAGE OverlappingInstances, FlexibleInstances #-}

instance Arbitrary (Tree a)
instance Arbitrary (Tree Int)

并且只有当 a 不是 Int 时，编译器才会 select Tree a 实例。但是，我建议不要这样做 - 如果您主要对测试 Tree Int 或一小部分 Tree 类型感兴趣，那么只需要这些类型的实例 - 没有 Tree a 的通用实例。

顺便说一句，我上面给出的生成器不是很好——它生成 Leaf 的时间正好是一半。原则上，我希望这种类型的生成器始终生成 "medium" 大小的树。实现这一点的一个简单方法是最初以高概率生成 Node，并随着树的增长逐渐降低该概率：

arbitraryTree :: (Ord a, Arbitrary a) => Float -> Float -> Gen (Tree a)
arbitraryTree c' f = do 
  x <- arbitrary 
  y <- suchThat arbitrary (>= x) 
  go x y c' 
   where 
    go mn mx c = frequency [(1000-q, return Leaf), (q, arbNode)] where
      q = round (1000 * c)

      arbNode = do 
        a <- suchThat arbitrary (\x -> x >= mn && x <= mx)
        l <- go mn a (c * f) 
        r <- go a mx (c * f) 
        return (Node l a r) 

instance (Ord a, Arbitrary a) => Arbitrary (Tree a) where 
  arbitrary = arbitraryTree 0.9 0.9

您可以使用 arbitraryTree 的参数来获得您喜欢的树。

生成任意范围的最小限制

Minimal restrictions to generate Arbitrary in range

haskell

testing

quickcheck