0votos

Generador de números en orden aleatorio (para practicar pruebas) en Haskell

por josejuan hace 6 años

No creo que haya nada más sencillo que un BUEN shufflé (con coste lineal y distribución uniforme, que no lo cumplen todas las implementaciones). Por jugar un poco, podemos obtener el mismo resultado (y con coste lineal aunque al usar factoriales bigint hace que sea peor) sabiendo que podemos indexar todas las permutaciones de N elementos. Entonces, basta tomar un número aleatorio entre 1 y N!. Tiene la ventaja de que podría transferirse esta información (el índice) y no la permutación (por red).

Este ejercicio es muy sencillo y es un buen ejemplo para practicar cómo escribir pruebas automáticas con herramientas XUnit. Se quiere implementar un método que permita calcular una secuencia de números aleatorios entre un rango de dos números enteros, de manera que dichos números aleatorios nunca se repitan.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
import Data.List 
import qualified Data.Map as M 
import Data.Map ((!)) 
import System.Random 
import Test.QuickCheck 
 
-- más información sobre esta función en 
--     http://kroker.emporia.edu/courses/2004/cs523s04/hand05/p296-campbell.pdf 
permutationFromIndex :: Integer -> Integer -> [Integer] 
permutationFromIndex m = g m 
  where g n i = if n == 1 then [0] else a ++ (n':b) 
                where n' = n - 1 
                      (q, r) = divMod i $ product [1..n'] 
                      (a, b) = splitAt (fromInteger q) $ permutationFromIndex n' r 
        f = M.fromList $ zip [0..] $ scanl1 (*) (1:[1..m]) 
 
 
-- así, obtener una secuencia desordenada con distribución uniforme podríamos hacer 
randomPermutation n = randomRIO (0, product [1..n] - 1) >>= return . permutationFromIndex n 
 
 
-- para testear, se pueden hacer diversas pruebas, por ejemplo, que una permutación de n elementos 
-- siempre devuelve n elementos diferentes 
test1 n i = length (permutationFromIndex n' i') == fromInteger n' 
            where n' = 1 + (n * n) `mod` 101 -- no más de 100 símbolos 
                  i' = i `mod` n'            -- un índice válido 
 
{-- 
 
  Haciendo 
  *Main> quickCheck test1 
  +++ OK, passed 100 tests. 
  *Main> _ 
 
--} 
 
-- otros test son posibles como que la distribución es uniforme, etc... 
3 comentarios
0votos

Escrito por Javier J. hace 6 años

Una solución estupenda josejuan, como siempre ;)

¿Cómo se suelen escribir las pruebas unitarias en Haskell? ¿También existe HaskellUnit?

Un saludo.
1votos

Escrito por josejuan hace 6 años

"¿Cómo se suelen escribir las pruebas unitarias en Haskell?"

Yo diría que los Haskellers no escriben muchas pruebas, el sistema de tipos de Haskell junto con la forma en que ellos las usan hacen que la probabilidad de que un código compilable falle sea pequeña.

Es muy conocida en el mundo Haskell la (más o menos) siguiente frase "Si tu código compila sin errores, es muy probable que haga lo que pretendías que hiciera"

Y a muchos novatos nos ha dado esa sensación, primero te vuelves un poco loco porque no entiendes nada, pero luego enseguida aprendes a aprovecharte de esa cualidad del lenguaje.

Eso no quita para que los haskellers escriban pruebas unitarias (sobre todo en entornos productivos), lo que pasa es que cuando las hacen, no suelen ser "pruebas de caso" (ej. Add(3, 4) == 7), sino que validan propiedades generales "de caja negra" que debe cumplir el código.

Eso hace que una pocas pruebas generales sean mucho más robustas que muchas de caso.

"¿También existe HaskellUnit?"

Probablemente la herramienta más popular sea QuickCheck, una fantástica herramienta que de forma trivialísima te permite probar casi cualquier propiedad.

Por ejemplo, supongamos que tienes una función f(x), y tu sabes que es una transformación lineal, entonces, puedes escribir un único test (que es sencillamente una función) que verifique la linealidad de tu transformación, es decir, que para todo a, b, x e y se cumple que test(a, b, x, y) = f(a * x + b * y) == a * f(x) + b * f(y), y hacer algo tan sencillo como
*Main> quickCheck test

Para que QuickCheck te testee (por defecto 100 veces) que se cumple tu propiedad tomando de forma totalmente automática valores aleatorios para el tipo de dato de tu función de test.

Es, sencillamente, genial. Obviamente no es una validación matemática, podría ocurrir que aun lanzando el test millones de veces no se detectara un error matemático, pero cada vez que lanzas el test se lanzan ¡pruebas diferentes! sobre ¡todo el dominio! de tu propiedad a testear. ¡Casi mágico!.

QuickCheck también provee de muchas otras herramientas para refinar el tipo de pruebas (por ejemplo, quizás sólo quieras valores positivos para tus argumentos, o de una enumeración, de un tipo de dato complejo, etc...).

Pero QuickCheck se suele usar de una forma "informal" (por lo inmediato) y no tiene carácter de plataforma de testing, para eso existe como bien apuntas HUnit, que sí lo he visto en diversos proyectos para validar el código.

¡Saludos! :)

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.