tl; dr: как вы пишете экземпляры Arbitrary, которые не взрываются, если ваш тип данных допускает слишком много вложенности? И как бы вы гарантировали, что эти экземпляры создают действительно случайные образцы вашей структуры данных?
Я хочу генерировать случайные древовидные структуры, а затем проверять определенные свойства этих структур после того, как я исказил их с помощью моего кода библиотеки. (NB: Я пишу реализацию алгоритма подтипирования, т.е. Учитывая иерархию типов, является типом A подтипом типа B. Это можно сделать произвольно сложным, включив в иерархию множественное наследство и обновления после инициализации Классический метод, который не поддерживает ни один из них, - это нумерация Шуберта, и последний известный мне результат - Alavi и др. 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 []]
снова не будет работать по той же причине. Можно было бы изменить параметр размера, чтобы сохранить длину списков вниз, но даже это не гарантирует прекращения, так как это еще несколько последовательных кубиков, и может получиться довольно плохо (и мне нужен нечетный node с 100 детьми.)
Это означает, что мне нужно ограничить размер всего дерева. Это не так прямолинейно. unordered-containers легко: просто используйте fromList. Это не так просто: как вы превращаете список в дерево, случайно и без какого-либо уклонения так или иначе (т.е. Не пользуясь левыми ветвями или деревьями, которые очень левны).
Какая-то конструкция ширины (функции, предоставляемые Data.Tree, все предзаказа) из списков были бы замечательными, и я думаю, что я мог бы написать один, но это оказалось бы нетривиальным. Поскольку я сейчас использую деревья, но позже буду использовать еще более сложные вещи, я подумал, что могу попытаться найти более общее и менее сложное решение. Есть ли это, или мне придется прибегнуть к написанию собственного нетривиального генератора Arbitrary? В последнем случае я мог бы просто прибегнуть к блок-тестам, так как это кажется слишком большой работой.
