restrictions minimales pour générer arbitraire dans la gamme

Question

Je voudrais générer de la valeur arbitraire pour la structure arborescente ordonnée dont le type est, par exemple

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

Une fonction que la valeur insère dans cet arbre tout en gardant ordonné, il faudrait que la valeur devrait être Ord. Mais pour générer des Arbres ordonnés pour une instance arbitraire, je devrais générer une valeur dans la plage "[low, hi]" et Ord est insuffisant pour cela. Donc j'ai aussi demandé que la valeur soit Enum puisque Enum permet d'obtenir des valeurs à partir d'une limite donnée. Le choose ci-dessous exige également 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 

donc de l'utiliser pour la mise en œuvre arbitrary je besoin des mêmes classes en classe arbitraire:

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

Ici, tout exigence Ord a => Tree a suffit structure de données elle-même, j'ai besoin (Arbitrary a, Ord a, Enum a, Rand.Random a) => Tree a pour son générateur. Cela ressemble à une fuite des détails de mise en œuvre dans la déclaration - probablement que je regarde mal, j'apprends Haskell. Mais il y a encore des questions:

1. Existe-t-il un moyen de déclarer un générateur plus générique qui n'a pas autant d'exigences?
2. Existe-t-il un moyen de déclarer une autre instance pour Arbitrary (Tree a) avec une instance supérieure qui aurait un ensemble d'exigences différent, quelque chose comme Arbitrary (Tree Int) qui serait utilisé uniquement pour Int?

Answer 1

Puisque vous voulez arbitraires commandés arbres, il n'y a pas moyen de se débarrasser de la contrainte Ord a dans l'instance Arbitrary (Tree a). Cependant, vous n'avez pas besoin de Enum ou Random (rappelez-vous que Arbitrary fait une génération de valeur aléatoire - donc naturellement vous ne devriez pas avoir besoin de Random aussi).

Voici comment j'implémenterais l'instance arbitraire.

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 

Notez que vous pouvez le rendre plus fiable en utilisant suchThatMaybe et fournissant une valeur par défaut si aucune valeur appropriée dans la plage se trouve dans un certain nombre d'essais.

Quant à votre deuxième question, vous pouvez en effet avoir les cas suivants:

{-# LANGUAGE OverlappingInstances, FlexibleInstances #-} 

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

et le compilateur sélectionner l'instance Tree a que si a n'est pas Int. Cependant, je déconseillerais ceci - si vous êtes principalement intéressé par le test Tree Int ou même un petit ensemble de types Tree, ayez juste des exemples pour ces types - aucune instance générale pour Tree a.

---

En aparté, je le générateur donné ci-dessus est pas très bon - il génère un Leaf exactement la moitié du temps. En principe, je voudrais qu'un générateur pour un type comme celui-ci produise toujours des arbres de taille "moyenne".Une façon simple de mettre en œuvre est d'avoir une forte probabilité de générer un Node initialement, et diminuer cette probabilité constante que l'arbre pousse:

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 

Vous pouvez jouer avec les paramètres à arbitraryTree pour obtenir des arbres que vous aimez .