QuickCheck

QuickCheck es una herramienta que el lenguaje de programación Haskell provee para poder probar las propiedades que deberían de cumplir las funciones, es decir, cada función tiene propiedades deseables lo que se logra con QuickCheck es ver si se cumplen total o parcialmente estas propiedades. Una ventaja notoria es que la propiedad es probada con una gran cantidad de casos generados aleatoriamente. Por ejemplo si tenemos una función suma:

suma x y = x + y 

para ver si cumple la propiedad conmutativa de la suma de números enteros, para cualquier entero:

prop_suma_conmutativa :: Int ->Int -> Bool prop_suma_conmutativa x y = suma x y == suma y x 

la función prop_suma_conmutativa al ser pasada como parámetro en quickCheck será verificada con varios casos aleatorios de enteros e indicará si eventualmente la función suma cumple o no la propiedad de la suma de números enteros.

Detalles Teóricos importantes

• QuickCheck toma como parámetro de entrada una propiedad
• Las propiedades son un conjunto de afirmaciones parametrizadas que en Haskell son funciones normales que pueden ser entendidas por cualquier compilador o intérprete
• Estas propiedades son verificadas con un número grande de casos de prueba generados de forma aleatoria
• Los programadores controlan la distribución de los casos de prueba generados con reglas condicionales y generadores
• Permite programar generadores propios
• Las funciones que deseamos probar pueden ser polimórficas pero las propiedades a probar deben ser monomórficas. El siguiente ejemplo muestra un error, por esto:

import Test.QuickCheck insertOrdered :: (Ord a) => a -> [a] -> [a] insertOrdered a [] = [a] insertOrdered a (x:xs)| a <= x = a:[x] ++ xs   | a > x = x: insertOrdered a xs prop_insertOrdered a (xs) = ordered(insertOrdered a xs) -- main = quickCheck prop_insertOrdered >:l Main Main> quickCheck prop_insertOrdered ERROR - Unresolved overloading 

Notar en este ejemplo:

• El nombre de la función para probar la propiedad, comienza con el prefijo prop_ (Ej. prop insertOrdered)esto es por convención.
• Se usó una función auxiliar ordered para probar la propiedad
• Podemos llamar la función quickCheck tanto en la línea de comandos como dentro de nuestro programa.
• Otro punto interesante a notar es que inclusive luego de añadir el tipo a la función, devuelve el siguiente mensaje “Falsifiable, after 3 tests”

Combinadores provistos por QuickCheck

Combinador condicional: Podemos mejorar un poco el ejemplo anterior añadiendo una condición, a nuestra propiedad.

prop_InsertOrdered :: Integer -> [Integer] -> Property prop_InsertOrdered x xs = ordered xs ==> ordered (insertOrdered x xs []) 

La estructura para utilizar el combinador condicional:

   <condition> ==> <property> 

• La introducción del combinador condicional ==> nos indica que solo se intentara probar la propiedad con casos que satisfagan la condición, si un candidato no satisface la condición es descartado y se probara con otro.
• Ahora el tipo devuelto de la función es Property
• Algunas veces la propiedad que es probada con condiciones, saca este mensaje Arguments exhausted after 55 tests. Esto suele suceder si la condición no es satisfecha y se han producido muchos casos que no satisfacen la propiedad, nos indica que por lo menos 55 casos pasaron la prueba, el programador decide aquí si esto es suficiente o no.

Combinador classify: El combinador classify no cambia el significado de la propiedad pero permite clasificar algunos casos, se podría decir que es una forma de etiquetarlos. En el ejemplo anterior veamos la cantidad de listas producidas aleatoriamente de tamaño menor a uno y listas mayores de dos elementos.

prop_InsertOrdered :: Int -> [Int] -> Property prop_InsertOrdered x xs = ordered xs ==>   classify (length xs <= 1) "lista de tam < 1" $   classify (length xs > 2) "lista de tam > 2" $   ordered (insertOrdered x xs) *Main> main OK, passed 100 tests. 79% lista de tam < 1. 4 % lista de tam > 2. *Main> 

La estructura para utilizar el combinador classify:

   classify <condition><string>$ <property> 

Como vemos solo un 4% de las listas generadas aleatoriamente son de tamaño mayor a dos.

Combinador collect: El combinador collect cosecha todos los valores que son pasados e imprime un histograma de esos, aquí podemos darnos cuenta que solo un porcentaje menor de casos de prueba son probados porque (en el caso específico) las listas de 1 o 0 elementos son ordenados pero los mayores a 2 elementos no lo son, este es un riesgo al utilizar leyes condicionales.

prop_InsertOrdered :: Int -> [Int] -> Property prop_InsertOrdered x xs = ordered xs ==>    collect (length xs >1)$    collect (length xs)$    ordered (insertOrdered x xs) *Main> main OK, passed 100 tests. 49% False, 0. 34% False, 1. 13% True, 2. 3% True, 3. 1% True, 4. 

La estructura para utilizar el combinador collect:

   collect <expression> $ <property> 

• Es importante investigar la proporción de los casos probados
• Lo que nos indica la salida es que: 49% de los casos no cumplen la expresión (length xs > 1) porque su tama˜no es 0,34% de los casos no cumplen la expresión (length xs > 1) porque su tama˜no es 1, etc.
• Una solución es que le pasemos un generador de listas ordenadas quickcheck nos facilita esto, al permitirnos crear generadores propios.

Combinador forAll: El combinador forAll nos indica que para toda lista ordenada se podrá probar la propiedad.

prop_InsertOrdered :: Integer -> Property prop_InsertOrdered x = forAll orderedList $ \ xs ->    collect (length xs>2)$    collect (length xs)$    ordered (insertOrdered x xs) -- el generador de listas ordenadas, -- solo es una funcion que crea listas ordenadas orderedList :: (Ord a, Arbitrary a) => Gen [a] orderedList = frequency [(1,return []), (4,do xs <- orderedList  n <- arbitrary  return ((case xs of   [] -> n   x:_ -> n ‘min‘ x)   :xs))] Main> main OK, passed 100 tests. 18% False, 1. 16% False, 0. 15% False, 2. 10% True, 8. 10% True, 3. 8% True, 4. 5% True, 5. 4% True, 9. 4% True, 13. 3% True, 6. 2% True, 7. 2% True, 11. 2% True, 10. 1% True, 16. 

La estructura para utilizar el combinador forAll:

   forAll <generator>$\<pattern> -> <property> 

• La salida nos indica que el 18% de las listas generadas aleatoriamente, por nuestro generador no es mayor a dos, su tamaño es uno, que el 1% de los casos generados por la funci´on orderedList(que genera listas ordenadas) si es mayor a dos y su tama˜no es 16.

• Notar que utilizamos el combinador frequency

Solo observando: Veamos la distribución de los casos de prueba...

prop_InsertOrdered :: Integer -> [Integer] -> Property prop_InsertOrdered x xs = ordered xs ==>   (length xs <= 1) ‘trivial‘   ordered (insertOrdered x xs) *Main> main OK, passed 100 tests (86% trivial). 

La estructura para ver la distribución es:

   <condition> ‘trivial‘ <property> 

Indicamos que las listas generadas por la funci´on orderedList son triviales en aquellos casos que su tamaño sea menor o igual a uno La respuesta nos dice que el 86% de los casos son triviales.

Definiendo Generadores Propios Para definir generadores propios para nuestros tipos de datos utilizamos la Clase Arbitrary.

data Insectos = Polillas  | Mariposas  | OtrosBichos instance Arbitrary Insectos where arbitrary = oneof [ return Mariposas,   return Polillas ,  return OtrosBichos] 

oneof: Podemos utilizar el combinador oneof escoge de una lista de generadores alternativos con una distribución uniforme, los constructores. frequency: Veamos la siguiente estructura, un árbol binario con dos funciones tam que nos devuelve el tamaño del árbol y arbolALista que nos devuelve los elementos de un árbol en una lista.

module ArbolBin where import Test.QuickCheck import Control.Monad -- necesitamos para la funciones  -- liftM, liftM2 data ArbolBin a = Hoja a  | Rama (ArbolBin a ) (ArbolBin a )  deriving Show tam :: ArbolBin Int -> Int tam (Hoja a) = 1 tam (Rama i d) = tam i + tam d arbolALista :: ArbolBin Int -> [Int] arbolALista (Hoja x) = [x] arbolALista (Rama i d )= arbolALista i ++ arbolALista d 

Una propiedad que nos gustaría que cumpla la función arbolALista es que el tamaño de la lista sea igual al tamaño del árbol.

 prop_arbolALista:: ArbolBin Int -> Bool prop_arbolALista t = length (arbolALista t )== tam t instance Arbitrary a => Arbitrary (ArbolBin a) where arbitrary = frequency [ (1,liftM Hoja arbitrary ),   (2,liftM2 Rama arbitrary arbitrary )] main = quickCheck prop_arbolALista 

El combinador frequency, que vimos anteriormente es del tipo:

   frequency :: [(Int, Gen a)] -> Gen a 

Su tipo nos dice que recibe una lista de generadores. Como primer parámetro la frecuencia con la que se escogerá cada generador y como segundo el generador en si. En el ejemplo del árbol binario se escogerá dos veces el generador para Rama y solo uno (de cada dos) para el generador de Hoja. En el ejemplo para la inserción para el combinador forAll nos dice que escogerá cuatro veces una lista diferente de vacío([])y una vez una lista vacía ([]).

Algo importante que hay que recalcar es que para utilizar de manera adecuada QuickCheck debemos saber que propiedades necesitamos que cumplan nuestras funciones.

 import Test.QuickCheck Definir Propiedades Opcionalmente definir generadores Main > quickCheck pro_definida 

•   Datos: Q2886113