Como usar 'oneof' em QuickCheck (Haskell)

Question

Eu estou tentando escrever um adereço que muda um Sudoku e verifica se ainda é válido.

No entanto, não estou certo de como usar o "oneof" -função corretamente. Você pode me dar algumas dicas, por favor?

prop_candidates :: Sudoku -> Bool
prop_candidates su = isSudoku newSu && isOkay newSu
    where
        newSu       = update su aBlank aCandidate
        aCandidate  = oneof [return x | x <- candidates su aBlank]
        aBlank      = oneof [return x | x <- (blanks su)]

Aqui estão mais algumas informações ...

type Pos = (Int, Int)
update :: Sudoku -> Pos -> Maybe Int -> Sudoku
blanks :: Sudoku -> [Pos]
candidates :: Sudoku -> Pos -> [Int]
[return x | x <- (blanks example)] :: (Monad m) => [m Pos]

Eu struggeled com este prop por 3 horas agora, para todas as idéias são bem-vindos!

Answer 1

O que eu queria chegar é que você tem um tipo de mix-up. Ou seja, aBlank não é um Pos, mas um Gen Pos, então update su aBlank aCandidate não faz sentido! Na verdade, o que você quer é uma maneira de gerar um novo sudoku dado um sudoku inicial; em outras palavras, uma função

similarSudoku :: Sudoku -> Gen Sudoku

Agora podemos escrevê-lo:

similarSudoku su = do aBlank <- elements (blanks su) 
                      -- simpler than oneOf [return x | x <- blanks su]
                      aCandidate <- elements (candidates su aBlank)
                      return (update su aBlank aCandidate)

ou ainda mais simples:

similarSudoku su = liftM2 (update su) (elements (blanks su)) (elements (candidates su aBlank))

e os olhares de propriedade como

prop_similar :: Sudoku -> Gen Bool
prop_similar su = do newSu <- similarSudoku su
                     return (isSudoku newSu && isOkay newSu)

Uma vez que existem casos

Testable Bool
Testable prop => Testable (Gen prop)
(Arbitrary a, Show a, Testable prop) => Testable (a -> prop)

Sudoku -> Gen Bool é Testable bem (assumindo instance Arbitrary Sudoku).

Answer 2

No meu blog, eu escrevi um simples craps simulador com QuickCheck testes que usam oneof para gerar rolos interessantes.

dizer que temos um super-simples Sudoku de uma única linha:

module Main where
import Control.Monad
import Data.List
import Test.QuickCheck
import Debug.Trace

type Pos = Int
data Sudoku = Sudoku [Char] deriving (Show)

No super-simples Sudoku deveria ter repetido valores:

prop_noRepeats :: Sudoku -> Bool
prop_noRepeats s@(Sudoku xs) =
  trace (show s) $ all ((==1) . length) $
                   filter ((/='.') . head) $
                   group $ sort xs

Você pode gerar um super-simples Sudoku com

instance Arbitrary Sudoku where
  arbitrary = sized board :: Gen Sudoku
    where board :: Int -> Gen Sudoku
          board 0 = Sudoku `liftM` shuffle values
          board n | n > 6 = resize 6 arbitrary
                  | otherwise =
                      do xs <- shuffle values
                         let removed = take n xs
                             dots = take n $ repeat '.'
                             remain = values \\ removed
                         ys <- shuffle $ dots ++ remain
                         return $ Sudoku ys

          values = ['1' .. '9']

          shuffle :: (Eq a) => [a] -> Gen [a]
          shuffle [] = return []
          shuffle xs = do x  <- oneof $ map return xs
                          ys <- shuffle $ delete x xs
                          return (x:ys)

O trace está lá para mostrar as placas gerados aleatoriamente:

*Main> quickCheck prop_noRepeats 
Sudoku "629387451"
Sudoku "91.235786"
Sudoku "1423.6.95"
Sudoku "613.4..87"
Sudoku "6..5..894"
Sudoku "7.2..49.."
Sudoku "24....1.."
[...]
+++ OK, passed 100 tests.

Answer 3

parece que aBlank :: Gen Pos que não coincide com a forma como é utilizado como um argumento de candidates :: Sudoku -> Pos -> [Int].

Eu estive olhando através aqui para encontrar um maneira de converter Gen a para a que permitem que você usá-lo com os candidatos. O melhor que eu podia ver é a função generate.

Diga-me se eu estou faltando alguma coisa ...