testing - programacion - QuickCheck: instancias arbitrarias de estructuras de datos anidados que generan muestras equilibradas

programacion ats estructuras

Question

tl; dr: ¿cómo se escriben instancias de Arbitrary que no explotan si su tipo de datos permite demasiado anidamiento? ¿Y cómo garantizaría que estas instancias produzcan muestras verdaderamente aleatorias de su estructura de datos?

Quiero generar estructuras de árbol aleatorias, luego probar ciertas propiedades de estas estructuras después de que las he destruido con mi código de biblioteca. (NB: estoy escribiendo una implementación de un algoritmo de subtipificación, es decir, dada una jerarquía de tipos, el tipo A es un subtipo de tipo B. Esto puede hacerse arbitrariamente complejo, al incluir actualizaciones de herencia múltiple y posteriores a la inicialización en la jerarquía El método clásico que no admite ninguno de estos es la numeración de Schubert, y el último resultado que conozco es Alavi et al. 2008.)

Tomemos el ejemplo de los rosales, siguiendo a Data.Tree :

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

Una instancia muy simple (y no lo intentes en casa) de Arbitray sería:

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

Como ya tiene una instancia Arbitrary según la restricción de tipo, y el Forest tendrá una, porque [] es una instancia, esto parece sencillo. No terminará (típicamente) por razones muy obvias: dado que las listas que genera son arbitrariamente largas, las estructuras se vuelven demasiado grandes, y existe una buena posibilidad de que no quepan en la memoria. Incluso un enfoque más conservador:

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

no funcionará, nuevamente, por la misma razón. Uno podría modificar el parámetro de tamaño para mantener baja la longitud de las listas, pero incluso eso no garantizará la finalización , ya que sigue siendo múltiples tiradas de dados consecutivas, y puede salir bastante mal (y quiero el nodo impar con 100 niños.)

Lo que significa que necesito limitar el tamaño de todo el árbol . Eso no es tan directo. unordered-containers lo tienen fácil: solo use fromList . Esto no es tan fácil aquí: ¿cómo se convierte una lista en un árbol, aleatoriamente, y sin incurrir en sesgos de una manera u otra (es decir, no favorecer ramas izquierdas, o árboles que son muy izquierdistas).

Algún tipo de construcción de amplitud (las funciones proporcionadas por Data.Tree son todas preordenar) de listas sería increíble, y creo que podría escribir una, pero resultaría no trivial. Ya que estoy usando árboles ahora, pero usaré cosas aún más complejas más adelante, pensé que podría tratar de encontrar una solución más general y menos compleja. ¿Hay alguno o tendré que recurrir a escribir mi propio generador Arbitrary no trivial? En este último caso, podría simplemente recurrir a pruebas unitarias, ya que esto parece demasiado trabajo.

Answer 1

Como mencionó Janis, puede usar el paquete testing-feat , que crea enumeraciones de tipos de datos algebraicos arbitrarios. Esta es la forma más fácil de crear generadores imparciales distribuidos uniformemente para todos los árboles de hasta un tamaño determinado.

Así es como lo usarías para los rosales:

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>

La instancia de Enumerable también se puede generar automáticamente con TemplateHaskell:

deriveEnumerable ''''Tree

Answer 2

Es posible que desee utilizar la biblioteca presentada en el documento "Feat: Enumeration funcional de tipos algebraicos" en el simposio Haskell 2012. Está en Hackage como prueba-feat, y un video de la charla que lo presenta está disponible aquí: http://www.youtube.com/watch?v=HbX7pxYXsHg

Answer 3

Utilice el sized :

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

(Adaptado de la presentación QuickCheck ).

PS Quizás esto genere árboles excesivamente equilibrados ...