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