I/O (input/output)

El problema con la pureza

Haskell es un lenguaje de programación puro, es decir:

• las funciones no pueden tener efectos externos. Por ejemplo, una función no puede imprimir nada en la pantalla. Las funciones solo pueden calcular su salida.
• las funciones no pueden depender de cosas externas. Por ejemplo, no pueden leer el teclado, o el sistema de archivos, o la red. Las funciones pueden solo depender de sus entradas. Dicho de otra forma, las funciones deben dar la misma salida para la misma entrada cada vez.

Pero… ¡a veces queremos hacer cosas así! Si la única cosa que pudieramos hacer con Haskell es escribir funciones para evaluarlas dentro de GHCi, sería interesante en teoría pero inútil en práctica.

De hecho, es posible hacer ese tipo de cosas en Haskell, pero es muy distinto a lo que se hace en otros lenguajes de programación.

El tipo IO

La solución a esa enigma es un tipo especial llamado IO. Los valores de tipo IO a son descripciones de cálculos con efectos, que, si los llevamos a cabo, harían (posiblemente) algunas operaciones con efectos de entrada y salida y (al final) producirían un valor de tipo a.

Hay un nivel de indirección acá que es esencial entender. Un valor de tipo IO a, en sí, es una cosa inerta, totalmente pura y sin efecto. Es solo la descripción de un cálculo con efecto. Una manera de pensarlo es como si fuera un programa imperativo.

Para ilustrar eso, supongamos que tenemos:

t :: Torta

¿Qué tenemos? Una torta deliciosa, por supuesto. Así de simple.

En comparación, supongamos que tenemos:

r :: Receta Torta

¿Qué tenemos? ¿Una torta? No, tenemos unas instrucciones para hacer una torta, solo un papel con algunas cosas escritas encima.

No solamente no tenemos una torta, sino que estamos teniendo una receta que no tiene ningun efecto sobre nada. Tener la receta a mano no hace que nuestro horno se va a prender o que la harina se va a repartir sobre la mesada, o algo por el estilo. Para efectivamente producir una torta, la receta debe ser seguida.

Del mismo modo, un valor de tipo IO a es solo una “receta” para producir algun valor de tipo a (y posiblemente tener algun efecto de paso). Como cualquier otro valor, puede ser pasado como argumento, devuelto como salida de una función, guardado en una estructura de datos, o (como vamos a ver pronto) combinado con otros valores IO en recetas más complejas.

Entonces, ¿cómo los valores de tipo IO a terminan siendo ejecutados? De una sola forma: el compilador Haskell busca un valor especial

main :: IO ()

que va a ser entregado al runtime y ejecutado. ¡Ya está! Podemos pensar en el runtime de Haskell como si fuera el chef que es el único con derecho a cocinar.

Si queremos que nuestra receta sea seguida entonces debemos hacer que sea parte de la receta grande (main) que es dada al chef. Por supuesto, main puede ser muy complicada, y típicamente va a ser compuesta de numerosos cálculos IO más pequeños.

Así que escribamos nuestro primer verdadero programa Haskell ejecutable. Podemos usar la función:

putStrLn :: String -> IO ()

que, dada una String, devuelve un cálculo IO que (cuando es ejecutado) imprime esa String en la pantalla. Entonces podemos poner lo siguiente en un archivo llamado Hello.hs:

main = putStrLn "Hello, Haskell!"

Luego, tipear runhaskell Hello.hs en línea de comando resulta en nuestro mensaje siendo impreso en la pantalla. También podemos usar ghc Hello.hs para producir un ejecutable llamado Hello (Hello.exe en Windows).

GHC busca un módulo llamado Main para encontrar la acción principal. Si no ponemos cabezera en un archivo Haskell, el nombre por defecto será Main, entonces eso funciona, por más que el archivo no se llama Main.hs. Si queremos usar un nombre de módulo distinto, tenemos que usar una opción en línea de comando para ghc o runhaskell. Por ejemplo si tenemos Something.hs:

module Something where
main :: IO ()
main = putStrLn "Hi out there!"

Lo podemos compilar con ghc -main-is Something Something.hs.

No hay una String “dentro de” un IO String

Muchos usuarios nuevos de Haskell terminan preguntando algo como “Tengo un IO String, ¿cómo lo convierto en una String?” o “¿Cómo consigo la String dentro del IO String?”.

Dadas las explicaciones anteriores, debería estar claro que estas preguntas no tienen sentido: un valor de tipo IO String es la descripción de algun cálculo, una receta, para generar una String. No hay String “dentro de” un IO String, no más que hya una torta “dentro de” una receta. Para producor una String (o una deliciosa torta), hace falta ejecutar el cálculo (o la receta). Y la única manera de hacerlo es darlo (posiblemente como parte de un valor IO más grande) al runtime de Haskell, a través de main.

Secuenciar acciones IO

Sería un poco tonto si un programa Haskell podría solamente hacer una cosa - la cosa que está en la acción main. Necesitamos una forma de hacer una cosa y luego otra. Haskell provee una notación especial para secuenciar acciones, llamada notación do.

Acá tenemos una acción que usa a notacion do para hacer pocas cosas. No la llamo main asi que solo puede ser accedida desde GHCi, pero está bien para lo que queremos hacer:

sillyExchange :: IO ()
sillyExchange = do
  putStrLn "Hello, user!"
  putStrLn "What is your name?"
  name <- getLine
  putStrLn $ "Pleased to meet you, " ++ name ++ "!"

Tipos IO

Antes de ver en detalle este ejemplo, miremos un poco los tipos. (En Haskell, siempre es útil mirar los tipos.)

Primero, empecemos por (). El tipo () se dice “unit” y tiene un solo valor, (). Es como si fuera definido con:

data () = ()

Aunque no es sintaxis Haskell válida. () es un tipo bastante tonto a primera vista: no transmite ninguna información, porque tiene solo un constructor sin argumento.

Pero es exactamente lo que necesitamos en ciertas acciones IO que no producen ningun valor al final. Haskell insiste que debe producir algo, entonces decimos que produce (). (Un poco como void en C/C++ o Java.)

Veamos otros tipos:

putStrLn :: String -> IO ()
getLine  :: IO String

Ya vimos el uso de putStrLn antes. Cuando secuenciamos acciones con la notación do , cada linea “desnuda” (lineas que no tienen un <- adentro) deben tener el tipo IO (). Por suerte, putStrLn "foo" tiene el tipo IO (). Esas acciones son ejecutadas en el orden de proceso de un bloque do.

getLine por otro lado, tiene como tipo IO String. Eso significa que getLine es una acción que produce una String. Para conseguir la String del getLine, usamos <- para dar un nombre nuevo a esa String. Hay una trampa: se puede hace solamente en un bloque do que define una acción IO. No hay forma útil de ejecutar getLine dentro de código que no es parte de una acción IO. Intentar eso sería como quitar la torta de la receta de torta…

Es importante ver que name <- getLine no tiene tipo; no es una expression Haskell. Es solo parte de la sintaxis de la notación do. No se puede incluir name <- getLine como parte de una expressión más grande, sino solo como linea de un bloque do.

Un ejemplo un poco más grande

jabber :: IO ()
jabber = do
  wocky <- readFile "jabberwocky.txt"
  let wockylines = drop 2 (lines wocky)  -- quita el titulo
  count <- printFirstLines wockylines
  putStrLn $ "There are " ++ show count ++ " stanzas in Jabberwocky."

printFirstLines :: [String] -> IO Int
printFirstLines ls = do
  let first_lines = extractFirstLines ls
  putStr (unlines first_lines)
  return $ length first_lines

extractFirstLines :: [String] -> [String]
extractFirstLines []         = []
extractFirstLines [_]        = []
extractFirstLines ("" : first : rest)
  = first : extractFirstLines rest
extractFirstLines (_ : rest) = extractFirstLines rest

Hay varias cosas intersantes por acá:

1. readFile :: FilePath -> IO String, donde type FilePath = String. Esta función lee el contenido entero de un archivo y lo guarda dentro de una String.

2. Sentencias let dentro de bloques do. La sentencia let en un bloque do permite crear un nombre nuevo atado a un valor puro. Observen la falta de in. Acuérdense que cuando decimos let x = y, x e y tienen el mismo tipo. Cuando decimos x <- y, y tiene un tipo como IO a, y entonces x tiene como tipo a.

3. return :: a -> IO a. Si necesitamos convertir un valor puro en una acción IO, usamos return. return es una función común y corriente en Haskell. ¡No es lo mismo que return en C/C++ o Java! Dentro de una acción IO, let x = y es lo mismo que x <- return y, pero lo anterior es mucho mejor: hace que la pureza de y sea más obvia.

Hay muchas funciones que podemos usar para hacer entrada y salida. Fijate en los módulos cuyo nombre empieza con System., en particular System.IO.

Mónadas

Motivación

Una mónada es algo práctico cuando uno quiere poner acciones en secuencia. Los detalles de la mónada dicen exactamente como las acciones deberían ser secuenciadas. Una mónada puede también almacenar información que puede ser leida y escrita mientras se llevan a cabo las acciones.

Ya conocemos IO. IO ocurre ser una mónada (así les decimos a tipos que son instancia de la clase Monad). Entonces el tipo IO pone en secuencia acciones de manera bastante natural, llevándolas a cabo en orden, y da a esas acciones el acceso para leer y escribir lo que sea, adonde sea. Vamos también a ver que Maybe y [] (pronunciado “lista”) son instancias de la clase Monad. Eso no nos da acceso a leer y escribir, pero nos permite hacer cosas interesantes con las secuencias.

La mejor manera de realmente entender las mónadas es de trabajar con ellas un buen rato. Después de programar usando varias mónadas distintas, serás capaz de abstraer la esencia de lo que es realmente una mónada. Para demostrarlo, veamos un ejemplo.

Queremos escribir una función que “zipea” juntos dos árboles binarios aplicándoles una función a los valores de cada nodo. Sin embargo, la función debe fallar totalmente si la estructura de los árboles es distinta. Con el término “fallar” queremos decir “devolver Nothing”. Acá va un primer intento:

data Tree a = Node (Tree a) a (Tree a)
            | Empty
              deriving (Show)

zipTree1 :: (a -> b -> c) -> Tree a -> Tree b -> Maybe (Tree c)
zipTree1 _ (Node _ _ _) Empty = Nothing
zipTree1 _ Empty (Node _ _ _) = Nothing
zipTree1 _ Empty Empty        = Just Empty
zipTree1 f (Node l1 x r1) (Node l2 y r2) =
    case zipTree1 f l1 l2 of
      Nothing -> Nothing
      Just l  -> case zipTree1 f r1 r2 of
                   Nothing -> Nothing
                   Just r  -> Just $ Node l (f x y) r

Este código anda, pero es poco elegante. Hemos anidado dos case con estructuras muy similares. Idealmente, para reducir la redundancia, queremos una función auxiliar como la siguiente:

bindMaybe :: Maybe a -> (a -> Maybe b) -> Maybe b
bindMaybe mx f = case mx of
                   Nothing -> Nothing
                   Just x  -> f x

Usando esta función, podemos tener un código más elegante:

zipTree2 :: (a -> b -> c) -> Tree a -> Tree b -> Maybe (Tree c)
zipTree2 _ (Node _ _ _) Empty = Nothing
zipTree2 _ Empty (Node _ _ _) = Nothing
zipTree2 _ Empty Empty        = Just Empty
zipTree2 f (Node l1 x r1) (Node l2 y r2) =
    bindMaybe (zipTree2 f l1 l2) $ \l ->
        bindMaybe (zipTree2 f r1 r2) $ \r ->
            Just (Node l (f x y) r)

Monad

¡Crealo o no, la función zipTree2 utiliza mónadas! La clase de tipos Monad es definida como sigue:

class Monad m where
  return :: a -> m a

   -- pronuncado "bind"
  (>>=) :: m a -> (a -> m b) -> m b

  (>>)  :: m a -> m b -> m b
  m1 >> m2 = m1 >>= \_ -> m2

Ya vimos return con IO. Acá vemos que se usa en cada mónada.

(>>=) (pronunciado “bind”) es donde ocurre la magia. Pensemos bien en su tipo:

(>>=) :: m a -> (a -> m b) -> m b

(>>=) toma dos parámetros. El primero es un valor de tipo m a. La idea es que es una acción de tipo m a representa un cómputo que resulta en un valor (o varias, o ninguna) de tipo a, y que puede tener algun “efecto”:

• c1 :: Maybe a es un cómputo que puede fallar pero resulta en un a si tiene éxito.
• c2 :: [a] es un cómputo que resulta en (varios) as.
• c3 :: Rand StdGen a es un cómputo que puede usar pseudoaleatoriedad y produce un a.
• c4 :: IO a es un cómputo que puede tener efectos de entrada/salida y luego produce un a.

Y así. Ahora, ¿qué tal el segundo parámetro de (>>=)? Es una función de tipo (a -> m b). Es decir, una función que va a elegir cuál es el siguiente cómputo en función del resultado del primero. Es precisamente ahí que se ve la idea de la mónada de encapsular cómputos que pueden ser puestos en secuencia.

Entonces todo lo que hace (>>=) es poner juntas dos acciones para producir una más grande, que lleva a cabo la primera y luego la segunda, devolviendo el resultado de la segunda. El giro importante acá es que nos toca decidir cuál acción ejecutar en segundo en función de la salida de la primera.

La implementación por defecto de (>>) ahora tiene sentido:

(>>)  :: m a -> m b -> m b
m1 >> m2 = m1 >>= \_ -> m2

m1 >> m2 simplemente hace m1 y luego m2, ignorando el resultado de m1.

Ejemplos

Empecemos escribiendo una instancia de Monad para Maybe:

instance Monad Maybe where
  return  = Just
  Nothing >>= _ = Nothing
  Just x  >>= k = k x

return, por supuesto, es Just. La implementación de (>>=) es igual a la de bindMaybe más arriba, pero el pattern matching se hace por casos de la función, y no por el uso de case. Si el primer parámetro de (>>=) es Nothing, entonces todo el cómputo falla; sino, si es Just x, aplicamos el segundo parámetro a x para decidir qué hacer después.

De paso, es común usar la letra k para el segundo parámetro de (>>=) porque “k” significa “continuación”.

Ahora que sabemos de mónadas, podemos escribir zipTree de forma más típica:

zipTree3 :: (a -> b -> c) -> Tree a -> Tree b -> Maybe (Tree c)
zipTree3 _ (Node _ _ _) Empty = Nothing
zipTree3 _ Empty (Node _ _ _) = Nothing
zipTree3 _ Empty Empty        = Just Empty
zipTree3 f (Node l1 x r1) (Node l2 y r2) =
    zipTree3 f l1 l2 >>= \l ->
        zipTree3 f r1 r2 >>= \r ->
            return (Node l (f x y) r)

La notación do que vimos andar con IO puede andar con cualquier mónada. Las flecha al revés son solo una sintaxis alternativa para los binds. Por ejemplo, considerá el bloque do siguiente:

addM :: Monad m => m Int -> m Int -> m Int
addM mx my = do
  x <- mx
  y <- my
  return $ x + y

GHC will desugar this directly to a version that explicitly uses (>>=):

addM' :: Monad m => m Int -> m Int -> m Int
addM' mx my = mx >>= \x -> my >>= \y -> return (x + y)

Usando la notación do, podemos refactorizar zipTree por última vez:

zipTree :: (a -> b -> c) -> Tree a -> Tree b -> Maybe (Tree c)
zipTree _ (Node _ _ _) Empty = Nothing
zipTree _ Empty (Node _ _ _) = Nothing
zipTree _ Empty Empty        = Just Empty
zipTree f (Node l1 x r1) (Node l2 y r2) = do
    l <- zipTree f l1 l2
    r <- zipTree f r1 r2
    return $ Node l (f x y) r

Ahí van más ejemplos:

check :: Int -> Maybe Int
check n | n < 10    = Just n
        | otherwise = Nothing

halve :: Int -> Maybe Int
halve n | even n    = Just $ n `div` 2
        | otherwise = Nothing

ex01 = return 7 >>= check >>= halve
ex02 = return 12 >>= check >>= halve
ex03 = return 12 >>= halve >>= check

O puede ser que te guste más de la forma siguiente:

ex04 = do
  checked <- check 7
  halve checked
ex05 = do
  checked <- check 12
  halve checked
ex06 = do
  halved <- halve 12
  check halved

La mónada de las listas

¿Y si hacemos una instancia Monad para el constructor de listas []?

instance Monad [] where
  return x = [x]
  xs >>= k = concatMap k xs

Un ejemplo simple:

addOneOrTwo :: Int -> [Int]
addOneOrTwo x = [x+1, x+2]

ex07 = [10,20,30] >>= addOneOrTwo
ex08 = do
  num <- [10, 20, 30]
  addOneOrTwo num

El Prelude de Haskell Prelude hasta define un bind al revés (=<<) con los argumentos invertidos:

ex09 = addOneOrTwo =<< [10,20,30]

Podemos pensar en la mónada de las listas como codificando cálculos con distintos resultados posibles. Más arriba, num representa los valores posibles [10, 20, 30] y luego es agregado a 1 o 2. El resultado es una lista de 6 elementos con todos los resultados posibles.

Ese no-determinismo puede ser explicitado con el uso de guardas, que terminan un cómputo si el parámetro no cumple alguna condición:

ex10 = do
  num <- [1..20]
  guard (even num)
  guard (num `mod` 3 == 0)
  return num

Acá, estamos eligiendo num dentro del rango de 1 a 20, y luego verificamos que es par y divisible por 3.

El tipo completo de guard es MonadPlus m => Bool -> m (). MonadPlus es otra clase (de Control.Monad) que caracteriza las mónadas que pueden fallar. Eso incluye Maybe y []. guard luego toma un valor Booleano pero no produce ningún resultado útil. Por eso su tipo de devolución es m () - ninguna información nueva sale de ella. Pero guard afecta la secuencia, así que es útil.

Combinadores de mónadas

Una cosa linda acerca de la clase Monad es que sólo usando return y (>>=) podemos construir muchos combinadores generales para programas con mónadas. Miremos algunos.

Primero, sequence toma una lista de valores monádicos y produce un solo valor monádico que colecta los resultados. Lo que significa realmente depende de cada mónada. Por ejemplo, en el caso de Maybe, significa que el cómputo general es exitoso solo si todos los cómputos individuales lo son; en el caso de IO significa que ejecuta todos los cómputos en secuencia.

sequence :: Monad m => [m a] -> m [a]
sequence [] = return []
sequence (ma:mas) = do
  a  <- ma
  as <- sequence mas
  return (a:as)

Usando sequence, uno puede escribir otros combinadores, como:

replicateM :: Monad m => Int -> m a -> m [a]
replicateM n m = sequence (replicate n m)

void :: Monad m => m a -> m ()
void ma = ma >> return ()

join :: Monad m => m (m a) -> m a
join mma = do
  ma <- mma
  ma

when :: Monad m => Bool -> m () -> m ()
when b action =
  if b
  then action
  else return ()

HUnit y QuickCheck

Tests unitarios

Supongamos que queremos fusionar dos listas ordenadas.

-- | Assuming the input lists are sorted, combine the lists into a
-- sorted output.
merge1 :: Ord a => [a] -> [a] -> [a]
merge1 (x:xs) (y:ys)
  | x < y     = x : merge1 xs ys
  | otherwise = y : merge1 xs ys
merge1 _      _      = []

¿Esta función anda como lo esperamos? Podríamos probarla unas veces en GHCi, pero es un poco insatisfactorio: tenemos que hacer el trabajo de pensar en un test, pero lo usamos solo una vez. En lugar de eso, es mucho mejor escribir el test dentro del archivo, de tal forma que lo puedamos volver a ejecutar cada vez que modificamos la función merge.

HUnit y QuickCheck proveen formas de testear nuestros programas. Los dos se enfocan en tests unitarios, donde solo una pequeña parte de un programa es escrutinada, en búsqueda de problemas.

HUnit nos da la posibilidad de ejecutar una función con cierta entrada y observar si produce la salida esperada. Hagámoslo para merge1:

test1_merge1 :: Test
test1_merge1 = "alternating numbers: [1,3,5] [2,4,6]" ~:
               merge1 [1,3,5] [2,4,6] ~?= [1,2,3,4,5,6]

Antes de analizar esa línea, corramos el test con runTestTT para ver qué pasa:

*Main> runTestTT test1_merge1
### Failure in: "alternating numbers: [1,3,5] [2,4,6]"
expected: [1,2,3,4,5,6]
 but got: [1,3,5]
Cases: 1  Tried: 1  Errors: 0  Failures: 1
Counts {cases = 1, tried = 1, errors = 0, failures = 1}

Uy. La función no anda. Qué sorpresa.

Afortunadamente, esta salida sirve. Nos dice el nombre del test, lo que se esperaba, y lo que pasó realmente. También hay un resumen abajo, por si hubieramos ejecutado varios tests, con solo algunos fallando.

Ahora, analicemos qué pasó. Empecemos, como de costumbre, con los tipos:

(~?=) :: (Show a, Eq a) => a -> a -> Test
(~:) :: Testable t => String -> t -> Test
runTestTT :: Test -> IO Counts

El operador (~?=) construye un Test comparando la igualdad de sus dos operandos, que deben ser “Show-ables”. Es exactamente lo que necesitamos, por un lado ponemos la llamada a la función que queremos testear, y por el otro la salida deseada. Por convención, el operador de test de HUnit pone un ? del lado de donde la falla podría ocurrir - así supo HUnit cuál valor era lo esperado y cuál fue el resultado real. HUnit también provee (~=?) que intervierte los argumentos (pero tiene el mismo tipo).

El operador (~:) sirve solamente para etiquetar los Tests con una String describiendo el test. Como HUnit soporta distintas formas de construir los tests, el tipo de (~:) permite cualquier tipo de la clase Testable; Test es seguramente Testable (como se puede ver en la documentación de HUnit). El test más arriba sería exitoso sin el uso de (~:), pero la salida sería menos útil. Además, (~?=) tiene una precedencia más alta que (~:), lo que significa que no necesitamos parentesis. (Podés pedir la precedencia de un operador en GHCi. Si ponés :info ~:, obtenés infixr 0 ~:, que significa que (~:) asocia a la derecha con la precedencia más baja posible.)

Finalmente, runTestTT es la función que corre los tests y produce la salida. También devuelve un valor de tipo Counts object, que es impreso en la última línea de la transcripción de GHCi que vimos más arriba - contiene un resumen del test, y sirve para ser operado si runTestTT es llamado desde otra función de un programa, por ejemplo main.

El tipo Test

HUnit exporta el detalle de su tipo Test:

data Test
  = TestCase Assertion
  | TestList [Test]
  | TestLabel String Test

Podés construir tests usando estos constructores. (Mirá la documentación para más información sobre Assertion.) El único que tiende a ser usado es TestList, que construye convenientemente un test maestro a partir de varios sub-tests.

test2_merge1 :: Test
test2_merge1 = TestList [ "one element: [1] []" ~:
                          merge1 [1] [] ~?= [1]
                        , test1_merge1 ]
```

    *Main> runTestTT test2_merge1
    ### Failure in: 0:"one element: [1] []"
    expected: [1]
     but got: []
    ### Failure in: 1:"alternating numbers: [1,3,5] [2,4,6]"
    expected: [1,2,3,4,5,6]
     but got: [1,3,5]
    Cases: 2  Tried: 2  Errors: 0  Failures: 2
    Counts {cases = 2, tried = 2, errors = 0, failures = 2}

Es una salida útil. No solo nos da los nombres, pero también las ubicaciones en las listas de tests.

HUnit tiene varias cosas más que pueden servir. Leé su documentación.

Antes de que nos pongamos a arreglar merge, nos ayudaría generalizar los tests, para que los puedamos correr sobre cualquier función merge, no solamente merge1 en particular. En general no lo vas a necesitar en tus tests, pero es un buen ejemplo de programación funcional.

type MergeFun = Ord a => [a] -> [a] -> [a]
test2 :: MergeFun -> Test
test2 merge = TestList [ "one element: [1] []" ~:
                         merge [1] [] ~?= [1]
                       , "alternating numbers: [1,3,5] [2,4,6]" ~:
                         merge [1,3,5] [2,4,6] ~?= [1,2,3,4,5,6]
                       ]

Bien. Ahora hagamos un mejor trabajo con merge. Parece que nos hemos olvidado de incluir el mayor de los dos elementos cuando comparamos.

merge2 :: MergeFun
merge2 all_xs@(x:xs) all_ys@(y:ys)
  | x < y     = x : merge2 xs all_ys
  | otherwise = y : merge2 all_xs ys
merge2 _             _             = []

*Main> runTestTT (test2 merge2)
### Failure in: 0:"one element: [1] []"
expected: [1]
 but got: []
### Failure in: 1:"alternating numbers: [1,3,5] [2,4,6]"
expected: [1,2,3,4,5,6]
 but got: [1,2,3,4,5]
Cases: 2  Tried: 2  Errors: 0  Failures: 2
Counts {cases = 2, tried = 2, errors = 0, failures = 2}

Esto es mejor (?). Ahora, no estamos perdiendo todo, pero no parece andar uan vez que una de las listas se acaba. Tratemos una vuelta más:

merge3 :: MergeFun
merge3 all_xs@(x:xs) all_ys@(y:ys)
  | x < y     = x : merge3 all_ys xs
  | otherwise = y : merge3 all_xs ys
merge3 xs            []            = xs
merge3 _             _             = []

*Main> runTestTT (test2 merge3)
Cases: 2  Tried: 2  Errors: 0  Failures: 0
Counts {cases = 2, tried = 2, errors = 0, failures = 0}

¡Huzzah!

Agreguemos otro test:

test3 :: MergeFun -> Test
test3 merge = "empty lists: [] []" ~:
              merge [] [] ~?= []

*Main> :load "09-testing.lec.lhs"
[1 of 1] Compiling Main             ( 09-testing.lec.lhs, interpreted )

/Users/rae/work/cis194/haskell/weeks/09-testing/09-testing.lec.lhs:194:17:
    No instance for (Ord a0) arising from a use of ‘merge’
    The type variable ‘a0’ is ambiguous
    Note: there are several potential instances:
      instance Integral a => Ord (GHC.Real.Ratio a)
        -- Defined in ‘GHC.Real’
      instance Ord Integer -- Defined in ‘integer-gmp:GHC.Integer.Type’
      instance Ord time-1.4.2:Data.Time.LocalTime.LocalTime.LocalTime
        -- Defined in ‘time-1.4.2:Data.Time.LocalTime.LocalTime’
      ...plus 28 others
    In the first argument of ‘(~?=)’, namely ‘merge [] []’
    In the second argument of ‘(~:)’, namely ‘merge [] [] ~?= []’
    In the expression: "empty lists: [] []" ~: merge [] [] ~?= []

/Users/rae/work/cis194/haskell/weeks/09-testing/09-testing.lec.lhs:194:29:
    No instance for (Show a0) arising from a use of ‘~?=’
    The type variable ‘a0’ is ambiguous
    Note: there are several potential instances:
      instance Show Double -- Defined in ‘GHC.Float’
      instance Show Float -- Defined in ‘GHC.Float’
      instance (Integral a, Show a) => Show (GHC.Real.Ratio a)
        -- Defined in ‘GHC.Real’
      ...plus 39 others
    In the second argument of ‘(~:)’, namely ‘merge [] [] ~?= []’
    In the expression: "empty lists: [] []" ~: merge [] [] ~?= []
    In an equation for ‘test3’:
        test3 merge = "empty lists: [] []" ~: merge [] [] ~?= []
Failed, modules loaded: none.

¡Puaj! ¿Qué pasó acá? El problema es que GHC no puede encontrar qué tipo quiere para nuestras listas vacías. A las instancias Show y Ord les importa mucho cuál es el tipo que elejimos, entonces GHC no quiere elegir para nosotros. Necesitamos una anotación de tipo para arreglar el problema:

test3 :: MergeFun -> Test
test3 merge = "empty lists: [] []" ~:
              merge [] [] ~?= ([] :: [Integer])

El :: [Integer] elige el tipo para nosotros, entonces GHC sabe qué hacer.

¿Ya hemos terminado? ¿Nuestra función es perfecta?

QuickCheck: tests basados en propiedades

Es aburrido escribir casos de tests. Y es fácil olvidarse de un comportamiento inesperado. Mucho mejor sería definir propiedades que queramos que nuestra función tenga. Luego, podríamos hacer que la computadora genere los casos de tests para nosotros.

QuickCheck es la librería estándar en Haskell para hacer tests basados en propiedades. La idea es que definís alguna propiedad, que luego se chequea usando datos pseudoaleatorios.

Por ejemplo:

prop_numElements_merge3 :: [Integer] -> [Integer] -> Bool
prop_numElements_merge3 xs ys
  = length xs + length ys == length (merge3 xs ys)

Esta propiedad dice que la suma de los tamaños de las listas de entrada debería ser la misma que el tamaño de la lista de salida. (Es costumbre empezar los nombres de propiedades con prop_.) ¡Probemos!

*Main> quickCheck prop_numElements_merge3
*** Failed! Falsifiable (after 5 tests and 4 shrinks): 
[]
[0]

(Tu resultado puede ser un poco distinto. Acordate que está usando aleatoriedad.)

La primera cosa que observamos es que nuestra función está claramente equivocada. Luego vemos que QuickCheck hizo 5 tests antes de descubrir un caso de tests fallando, entonces nuestra función no es tan mala. QuickCheck nos dice que los parámetros que fallan son [] y [0]. Efectivamente, GHCi nos dice que merge3 [] [0] es [], lo que es falso.

Lo lindo acá es que QuickCheck nos encontró un caso de test pequeño que demuestra que nuestra función está equivocada. La manera de hacerlo es que usa una técnica llamada shrinking (encogimiento). Despúes de encontrar un caso de test que causa una falla, QuickCheck intenta buscando parámetros cada vez más pequeños que sigan produciendo una falla. Es maravilloso, porque sino QuickCheck nos generaría casos inmanejables y difíciles de tomar en cuenta.

Una nota final sobre esta propiedad es que la signatura de tipo nos dice que la propiedad toma listas de enteros, no cualquier tipo a. Esto es para que GHC no elija un tipo tonto, como (). Debemos siempre tener cuidado con eso cuando escribimos propiedades sobre funciones polimórficas. Los números son siempre una buena elección.

Implicaciones

Como lo hicimos arriba, generalicemos nuestro tests sobre implementaciones de nuestra operación de fusión. Otra vez, probablemente no sea necesario que lo hagas.

prop_numElements :: MergeFun -> [Integer] -> [Integer] -> Bool
prop_numElements merge xs ys
  = length xs + length ys == length (merge xs ys)

E intentamos otra vez con nuesta función:And, we take another stab at our function:

merge4 :: MergeFun
merge4 all_xs@(x:xs) all_ys@(y:ys)
  | x < y     = x : merge4 xs all_ys
  | otherwise = y : merge4 all_xs ys
merge4 xs            ys            = xs ++ ys

*Main> quickCheck (prop_numElements merge4)
+++ OK, passed 100 tests.

¡Huzzah!

¿Ya está? ¿Hemos terminado? Todavía no. Intentemos otra propiedad:

prop_sorted1 :: MergeFun -> [Integer] -> [Integer] -> Bool
prop_sorted1 merge xs ys
  = merge xs ys == sort (xs ++ ys)

*Main> quickCheck (prop_sorted1 merge4)
*** Failed! Falsifiable (after 4 tests and 3 shrinks): 
[]
[1,0]

Rayos. QuickCheck, razonablemente, intentó con la lista [1,0]. Por supuesto, no va a funcionar porque no está ordenada. Necesitamos especificar una propiedad de implicación:

prop_sorted2 :: MergeFun -> [Integer] -> [Integer] -> Property
prop_sorted2 merge xs ys
  = isSorted xs && isSorted ys ==> merge xs ys == sort (xs ++ ys)

isSorted :: Ord a => [a] -> Bool
isSorted (a:b:rest) = a <= b && isSorted (b:rest)
isSorted _          = True    -- must be fewer than 2 elements

En prop_sorted, vemos que usamos el operador (==>). Su tipo es Testable prop => Bool -> prop -> Property. (Es un Testable distinto del de HUnit.) Toma un Bool y un Testable y produce un Property. Observá como prop_sorted devuelve un Property, no un Bool. Vamos a poner orden en estos tipos más adelante, pero es interesante la aparición de Property acá.

Veamos como esto funciona:

*Main> quickCheck (prop_sorted2 merge4)
*** Gave up! Passed only 21 tests.

(Eso tomo capaz 20 segundos.) No hay ninguna falla, pero no hay muchos éxitos tampoco. El problema es que QuickCheck va a ejecutar el test solamente cuando las dos listas generadas aleatoriamente de tamaño n son ordenadas. Pero la probabilidad de que eso pase es de 1/n!, lo que es, en general, muy bajo. Y además necesitamos dos listas ordenadas. Eso no va a funcionar bien.

Los tipos de QuickCheck

¿Cómo hace QuickCheck para generar los casos arbitrarios? Usa la clase Arbitrary:

class Arbitrary a where
  arbitrary :: Gen a
  shrink    :: a -> [a]

Dejemos shrink a la documentación en línea, y enfoquemonos en arbitrary. La función arbitrary nos da un Gen a - un generador para el tipo a. Por supuesto, a la función arbitrary para listas no le importa el ordenamiento (de hecho, no le puede importar, dada la parametricidad), pero a nosotros sí. Por suerte, es un problema común, y QuickCheck provee una solución bajo la forma de un OrderedList, un envoltorio alrededor de listas que tiene la instancia Arbitrary que necesitábamos:

newtype OrderedList a = Ordered { getOrdered :: [a] }
instance (Ord a, Arbitrary a) => Arbitrary (OrderedList a) where ...

(newtype es casi igual a data. Buscá en línea para más información.)

Ahora, reescribamos nuestra propiedad:

prop_sorted3 :: MergeFun
             -> OrderedList Integer -> OrderedList Integer -> Bool
prop_sorted3 merge (Ordered xs) (Ordered ys)
  = merge xs ys == sort (xs ++ ys)

*Main> quickCheck (prop_sorted3 merge4)
+++ OK, passed 100 tests.

¡Huzzah! Solo cambiando un poco los tipos, podemos afectar la selección de la instancia para conseguir lo que queríamos.

Sí, todo esto parece magia negra. ¿Cómo hace QuickCheck? Veamos más en detalle los tipos.

quickCheck :: Testable prop => prop -> IO ()

class Testable prop where ...
instance Testable Bool where ...
instance Testable Property where ...
instance (Arbitrary a, Show a, Testable prop) => Testable (a -> prop) where ...

Podemos quickCheck-ear cualquier cosa que sea Testable. Los valores Booleanon son Testable, tanto como el misterioso Property. Pero es la última instancia de Testable que nos llama la atención. Dice que una function es Testable siempre y cuando su parámetro tiene una función arbitrary, su parámetro puede ser mostrado (en caso de falla) y el restultado es Testable.

¿Es Testable [Integer] -> [Integer] -> Bool? Por supuesto. Recordá que [Integer] -> [Integer] -> Bool es equivalente a [Integer] -> ([Integer] -> Bool). Porque [Integer] tiene las instancias para Arbitrary y Show, podemos usar la última instancia más arriba siempre y cuando [Integer] -> Bool es Testable. Y eso es Testable porque tenemos (otra vez) una instancia Arbitrary y Show para [Integer], y Bool es Testable. Entonces, así es como quickCheck trabaja - utiliza las instancias de Arbitrary para los tipos de los parámetros. Y, así es como cambiar los tipos de argumentos de OrderedList Integer nos produjo el resultado que queríamos.

Generando datos arbitrarios

Cuando querés usar QuickCheck sobre tus propios tipos de datos, es necesario escribir una instancia Arbitrary para ellos. Ahora, veamos como hacerlo.

Supongamos que tenemos un tipo personalizado de listas:

data MyList a = Nil | Cons a (MyList a)

instance Show a => Show (MyList a) where
  show = show . toList
  
toList :: MyList a -> [a]
toList Nil           = []
toList (a `Cons` as) = a : toList as

fromList :: [a] -> MyList a
fromList []     = Nil
fromList (a:as) = a `Cons` fromList as

Si queremos una instancia para Arbitrary, debemos definir la función arbitrary, de tipo Gen (MyList a). Por suerte para nosotros, Gen es una mónada, asi que algunos detalles ya son familiares. Tambíen nos damos cuenta que si queremos una lista arbitraria de a, vamos a necesitar generar valores a arbitrarios. Entonces, nuestra instancia se parece a:

instance Arbitrary a => Arbitrary (MyList a) where
  arbitrary = genMyList1 

A esta algura, es necesario chequear los combinadores disponibles en la sección “Generator combinators” de la documentación de QuickCheck.

Es útil pensar cómo vos, un ser humano, haría para generar una lista arbitraria. Una manera de hacerlo es elegir un tamaño arbitrario (por ejemplo, entre 0 y 10), y luego elegir cada elemento de manera arbitraria. Acá tenemos una implementación:

genMyList1 :: Arbitrary a => Gen (MyList a)
genMyList1 = do
  len <- choose (0, 10)
  vals <- replicateM len arbitrary
  return $ fromList vals

Probamos:

*Main> sample genMyList1
[(),(),(),(),(),()]
[]
[(),(),(),(),(),(),(),(),()]
[(),(),(),(),(),()]
[(),(),(),(),(),(),(),(),()]
[()]
[(),(),(),(),(),(),(),()]
[(),(),(),(),(),(),(),(),()]
[(),(),()]
[(),(),(),(),(),()]
[(),(),(),(),(),(),(),(),(),()]

Los tamaños arbitrarios funcionan, pero la generación de elementos luce muy aburrida. Usemos una anotación de tipo para hacerlo más interesante!

*Main> sample (genMyList1 :: Gen (MyList Integer))
[0,0,0,0,0,0,0,0,0,0]
[]
[-2,3,1,0,4,-1]
[-5,0,2,1,-1,-3]
[-5,-6,-7,-2,-8,7,-3,4,-6]
[4,-3,-3,2,-9,9]
[]
[10,-1]
[9,-7,-16,3,15]
[0,14,-1,0]
[3,18,-13,-17,-20,-8]

Mucho mejor.

Pero esta generación todavia no es genial, porque puede ser que una función escrita para MyList falle solo con listas mayores a 10 elementos. Deseamos tamaños sin límites. Hay una manera de hacerlo:

genMyList2 :: Arbitrary a => Gen (MyList a)
genMyList2 = do
  make_nil <- arbitrary
  if make_nil    -- type inference tells GHC that make_nil should be a Bool
     then return Nil
     else do
       x <- arbitrary
       xs <- genMyList2
       return (x `Cons` xs)

*Main> sample (genMyList2 :: Gen (MyList Integer))
[0,0,0,0,0,0]
[]
[3,-3]
[]
[]
[-1,-1]
[-10]
[]
[]
[11]
[-20,-14]

Los tamaños no tienen límite (me vas a tener que creer), pero estamos consiguiendo muchas listas vacías. Eso es porque en cada nodo de una lista, tenemos un 50% de probabilidad de producir Nil. Eso significa que una lista de tamaño n va a aparecer cada 2^n veces. Entonce, los tamaños no son acodatos pero son muy poco probables.

La forma de progresar acá es de utilizar el combinador sized. QuickCheck está configurado para probar con cosas arbitrarias “simples” antes de “complejas”. La manera de hacerlo es usando un parámetro de tamaño, interno a la mónada Gen. Cuanto más generador es QuickCheck, más alto se vuelve ese parámetro. Queremos usar el parámetro de tamaño para hacer nuestra generación.

Miremos el tipo de sized:

sized :: (Int -> Gen a) -> Gen a

La mejor forma de explicar como funciona es con un ejemplo:

genMyList3 :: Arbitrary a => Gen (MyList a)
genMyList3 = sized $ \size -> do
  len <- choose (0, size)
  vals <- replicateM len arbitrary
  return $ fromList vals

*Main> sample (genMyList3 :: Gen (MyList Integer))
[]
[-2]
[-1,3,4]
[-4,-2,1,-1]
[]
[]
[12,3,11,0,3,-12,10,5,11,12]
[-4,-8,-9,2,14,5,8,11,-1,7,11,-8,2,-6]
[6,10,-5,15,6]
[-3,-18,-4]
[9,19,13,-19]

Esto anduvo lindo - las listas tienden a volverse más larga a medida que aparecen tarde. La idea es que sized toma una continuación: la cosa que hay que hacer con el parámetro. Solo usamos una función lambda como argumento de sized. Si es demasiado complicado (por ejemplo solo queremos producir el parámetro de tamaño, sin usar una continuación), siempre podés hacer algo como lo siguiente:

getSize :: Gen Int
getSize = sized return

Te dejo entender vos mismo como esto funciona. ¡Seguí los tipos!

Como último ejemplo, podemos también elegir generadores arbitrarios a partir de una lista basada sobre la frecuencia. Por más que la función length de genMyList3 ande bien con listas, la técnica siguiente sería mucho mejor para árboles:

genMyList4 :: Arbitrary a => Gen (MyList a)
genMyList4 = sized $ \size -> do
  frequency [ (1, return Nil)
            , (size, do x <- arbitrary
                        xs <- {- resize (size - 1) -} genMyList4
                        return (x `Cons` xs) )]

*Main> sample (genMyList4 :: Gen (MyList Integer))
[]
[2,0]
[4,0,-1]
[-6,-2,3,-1,-1]
[6,6]
[2,2,2,6,6]
[-6,-9,5,-5]
[8,7,5,7,7,-1,-2,-1,-5,-3]
[15,-12,14,13,-5,-10,-9,-8,-2]
[12,-11,-8,6,-6,-4,11,11]
[-7,1,-3,4,-3,-9,4,6,-2,10,-9,-7,5,7,1]

Miremos el tipo de frequency:

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

Toma una lista de pares (Int, Gen a) y produce un Gen a. Los números en la lista nos dan la probabilidad de elegir ese elemento. Arriba, hemos fijado la frecuencia de Nil a 1, pero hacemos que la probabilidad de Cons varie en función del tamaño deseado. Luego, en la llamada recursiva a genMyList4, usamos resize para bajar el parámetro size. Sino, es demasiado probable de generar una lista que tiende a tener un tamaño infinito.

Más ejemplos con QuickCheck

• http://www.glc.us.es/~jalonso/vestigium/i1m2013-verificacion-de-la-ordenacion-por-mezcla-con-quickcheck/
• http://www.glc.us.es/~jalonso/vestigium/i1m2016-estadistica-descriptiva-en-haskell/
• http://www.glc.us.es/~jalonso/vestigium/i1m2015-ejercicios-del-cifrado-cesar/