QuickCheck: произвольные экземпляры вложенных структур данных, которые генерируют сбалансированные образцы

tl; dr: как вы пишете экземпляры Arbitrary которые не взрываются, если ваш тип данных допускает слишком много гнездования? И как бы вы гарантировали, что эти экземпляры создают действительно случайные образцы вашей структуры данных?

Я хочу генерировать случайные древовидные структуры, а затем проверять определенные свойства этих структур после того, как я исказил их с помощью моего библиотечного кода. (NB: Я пишу реализацию алгоритма подтипирования, т. Е. Учитывая иерархию типов, является типом A подтипом типа B. Это можно сделать произвольно сложным, включив в иерархию множественное наследство и обновления после инициализации Классический метод, который не поддерживает ни одно из них, - это нумерация Шуберта, и последний известный мне результат - Alavi et al., 2008.)

Давайте возьмем пример розовых деревьев, следуя Data.Tree :

data Tree a = Node a (Forest a)
type Forest a = [Tree a]

Очень простой (и не пытающийся на дому) экземпляр Arbitray был бы:

instance (Arbitrary a) => Arbitrary (Tree a) where
    arbitrary = Node <$> arbitrary <$> arbitrary

Так a уже есть Arbitrary экземпляр в соответствии с типом ограничения, и у Forest будет один, потому что [] является экземпляром тоже, это кажется прямым. Он не будет (как правило) прекращаться по очень очевидным причинам: поскольку создаваемые им списки произвольно длинны, структуры становятся слишком большими, и есть хорошие шансы, что они не будут вписываться в память. Даже более консервативный подход:

arbitrary = Node <$> arbitrary <*> oneof [arbitrary,return []]

не будет работать, опять же, по той же причине. Можно было бы изменить параметр размера, чтобы сохранить длину списков вниз, но даже это не гарантирует прекращения , так как это еще несколько последовательных кубиков, и может получиться довольно плохо (и я хочу, чтобы нечетный узел со 100 дети.)

Это означает, что мне нужно ограничить размер всего дерева . Это не так прямолинейно. unordered-containers легко: просто используйте fromList . Здесь не так просто: как вы превращаете список в дерево, случайно и без какого-либо уклонения так или иначе (т. Е. Не пользуясь левыми ветвями или деревьями, которые очень левые).

Какая-то конструкция ширины (функции, предоставляемые Data.Tree , все предварительные) из списков были бы потрясающими, и я думаю, что я мог бы написать один, но это оказалось бы нетривиальным. Поскольку я сейчас использую деревья, но позже буду использовать еще более сложные вещи, я подумал, что могу попытаться найти более общее и менее сложное решение. Есть ли это, или мне придется прибегнуть к написанию собственного нетривиального генератора Arbitrary чисел? В последнем случае я мог бы просто прибегнуть к блок-тестам, так как это кажется слишком большой работой.

Всего 3 ответа


Использовать размер :

instance Arbitrary a => Arbitrary (Tree a) where
arbitrary = sized arbTree

arbTree :: Arbitrary a => Int -> Gen (Tree a)
arbTree 0 = do
    a <- arbitrary
    return $ Node a []
arbTree n = do
    (Positive m) <- arbitrary
    let n' = n `div` (m + 1)
    f <- replicateM m (arbTree n')
    a <- arbitrary
    return $ Node a f

(Адаптировано из презентации QuickCheck ).

PS Возможно, это создаст слишком сбалансированные деревья ...


Возможно, вы захотите использовать библиотеку, представленную в документе «Feat: Functional Enumeration of Algebraic Types» на симпозиуме Haskell 2012. Он находится в Hackage как тест-подвиг, а видео с сообщением об этом можно найти здесь: http: /www.youtube.com/watch?v=HbX7pxYXsHg


Как упоминал Янис, вы можете использовать тестирование пакетов -feat , которое создает перечисления произвольных типов алгебраических данных. Это самый простой способ создания несмещенных равномерно распределенных генераторов для всех деревьев до заданного размера.

Вот как вы могли бы использовать его для розовых деревьев:

 import Test.Feat (Enumerable(..), uniform, consts, funcurry) import Test.Feat.Class (Constructor) import Data.Tree (Tree(..)) import qualified Test.QuickCheck as QC -- We make an enumerable instance by listing all constructors -- for the type. In this case, we have one binary constructor: -- Node :: a -> [Tree a] -> Tree a instance Enumerable a => Enumerable (Tree a) where enumerate = consts [binary Node] where binary :: (a -> b -> c) -> Constructor c binary = unary . funcurry -- Now we use the Enumerable instance to create an Arbitrary -- instance with the help of the function: -- uniform :: Enumerable a => Int -> QC.Gen a instance Enumerable a => QC.Arbitrary (Tree a) where QC.arbitrary = QC.sized uniform -- QC.shrink = <some implementation> 

Экземпляр Enumerable также может быть сгенерирован автоматически с помощью TemplateHaskell:

deriveEnumerable ''Tree

Есть идеи?

10000