Минимальные ограничения для генерации произвольного диапазона

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

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

Функция, которая вставляет значение в это дерево, сохраняя его упорядоченным, потребует, чтобы это значение было Ord. Но для создания упорядоченных деревьев для произвольного экземпляра мне нужно было бы сгенерировать значение в диапазоне «[low, hi]», а Ord для этого недостаточно. Поэтому я также потребовал, чтобы значение было 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, мне нужны те же классы в произвольном классе:

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. Но все же есть вопросы:

  1. Есть ли способ объявить более общий генератор, у которого не так много требований?
  2. Есть ли способ объявить другой экземпляр для Arbitrary (Tree a) вместе с указанным выше, который будет иметь другой набор требований, что-то вроде Arbitrary (Tree Int), который будет использоваться только для Int?

testing haskell quickcheck
person Petr Gladkikh    schedule 23.03.2015    source источник
comment
Вы можете генерировать деревья с помощью произвольных операций над деревом. Для этого требуется только экземпляр Arbitrary для a и не требуется доступ к реализации этих операций.   -  person Cirdec    schedule 23.03.2015

Ответы (1)


arrow_upward
4
arrow_downward

Поскольку вам нужны произвольные упорядоченные деревья, нет способа избавиться от ограничения Ord a в экземпляре Arbitrary (Tree 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)

и компилятор выберет экземпляр Tree a, только если a не Int. Однако я бы не советовал этого делать — если вы в основном заинтересованы в тестировании Tree Int или даже небольшого набора типов Tree, просто создайте экземпляры для этих типов, а не общий экземпляр для Tree a.

Кстати, генератор, который я привел выше, не очень хорош — он генерирует Leaf ровно в половине случаев. В принципе, я хотел бы, чтобы генератор для такого типа всегда генерировал деревья "среднего" размера. Простой способ реализовать это — изначально иметь высокую вероятность генерации 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, чтобы получить деревья, которые вам нравятся.

person user2407038    schedule 23.03.2015
comment
Я вижу, что такой вариант не очень эффективен, поскольку он перебирает все доступные значения, пока не найдет подходящее. Это кажется стоимостью устранения предположений, приемлемой для тестов. - person Petr Gladkikh; 24.03.2015