Cómo utilizar 'oneof' en quickCheck (Haskell)

Question

Estoy tratando de escribir un objeto que cambia un Sudoku y luego compruebo si todavía es válido.

Sin embargo, no estoy seguro de cómo usar la función "oneof" correctamente. ¿Puedes darme algunas pistas, 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)] 

Éstos son algunos más información ...

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] 

He struggeled con este apoyo durante 3 horas ahora, para que todas las ideas son bienvenidas!

Answer 1

Lo que quería ir a parar es que tiene un tipo de confusión. A saber, aBlank no es Pos, pero Gen Pos, entonces update su aBlank aCandidate no tiene sentido! De hecho, lo que desea es una forma de generar un nuevo sudoku dado un sudoku inicial; en otras palabras, una función

similarSudoku :: Sudoku -> Gen Sudoku 

Ahora podemos escribir:

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) 

o incluso más simple:

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

y la propiedad parece

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

Desde allí son instancias

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

Sudoku -> Gen Bool es Testable así (suponiendo instance Arbitrary Sudoku).

Answer 2

En mi blog, escribí un simple craps simulator con pruebas QuickCheck que usan oneof para generar rollos interesantes.

Digamos que tenemos un super-sencilla Sudoku de una sola fila:

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

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

valores

Sin súper sencilla Sudoku debería haber repetido:

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

Usted podría generar un Sudoku súper sencillo con

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) 

el trace es allí para mostrar el verraco generado aleatoriamente DS:

*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 no coincide con la forma en que se utiliza como un argumento de candidates :: Sudoku -> Pos -> [Int].

He estado buscando a través de here para encontrar una forma de convertir Gen a en a que le permitiría usarlo con los candidatos. Lo mejor que pude ver es la función generate.

Dime si me falta algo ...