Volver a la página de la materia

• Lectura recomendada: Tutorial de Haskell

Hicimos un repaso de las formas básicas de definir funciones con sus respectivas aridades (el tipo de la función). Vimos cómo usar análisis por casos y pattern matching sobre listas y números. Vimos cómo definir funciones polimórficas.

  fac :: Int -> Int
  fac 0 = 1
  fac (n+1) = (n+1) * fac n

  len :: [a] -> Int                                                                               
  len [] = 0                                                                                      
  len (_:xs) = 1 + length xs                                                                      

Vimos cómo abrir el intérprete de Haskell y cómo crear, editar y cargar archivos de definiciones.

• Lectura recomendada:
  • Tutorial de Haskell: 2 Valores, Tipos, y otras Golosinas
  • 5 Clases de tipos y Sobrecarga

Vimos cómo definir tipos enumerados:

  data Color = Red | Green | Blue

Vimos cómo escribir funciones que usen estos nuevos tipos usando pattern matching. Vimos cómo hacer que dos colores puedan ser comparados con ==. Para esto vimos la clase Eq del Prelude de Haskell (abrir con “:f ==”):

  class Eq a where                                                                                
      (==) :: a -> a -> Bool

Y vimos que debemos instanciar esta clase para el tipo Color (o sea, definir == ):

  instance Eq Color where
      Red == Red = True
      Green == Green = True
      Blue == Blue = True
      _ == _ = False

También vimos cómo hacer para definir un orden sobre los colores y que se puedan comparar con <, ⇐, >= y >. Para esto vimos la clase Ord del Prelude de Haskell (abrir con “:f <”):

  class  (Eq a) => Ord a  where
      (<), (<=), (>=), (>)  :: a -> a -> Bool
      max, min              :: a -> a -> a 

Y vimos que debemos instanciar esta clase para el tipo Color:

  instance Ord Color where
      Red <= _ = True
      Green <= x = x /= Red
      Blue <= x = x == Blue

Vimos que alcanza con definir sólo el ⇐ para que todas las demás funciones de comparación queden definidas.

Finalmente explicamos para qué sirven las clases en general: Las clases sirven para definir funciones polimórficas (que funcionen para varios tipos distintos). En las funciones, en vez de poner un tipo concreto, ponemos la clase que tiene las operaciones que necesitamos usar. Todo tipo que instancie esa clase va a poder ser usado con esta función. Por ejemplo, si definimos la función “lmax”, que devuelve el máximo de una lista, con aridad

  lmax :: Ord a => [a] -> a

esta función va a funcionar con listas con cualquier tipo que instancie la clase Ord, inclusive el tipo Color.

Resumen de conceptos vistos:

• Tipo: Un conjunto de valores posibles. Estos valores pueden ser tomados y devueltos por las funciones.
• Clase: Una lista de nombres de funciones con sus respectivas aridades. En las aridades aparece un tipo genérico que va a ser reemplazado por tipos concretos en las instancias de la clase. Algunas funciones pueden estar definidas en términos de otras pero siempre va a faltar alguna definición.
• Instancia de una clase en un tipo: Definición concreta de las funciones de la clase para que funcionen con este tipo. En las aridades se reemplaza el tipo genérico por el tipo dado. Luego de la instanciación, las funciones de la clase se pueden usar con este tipo.
• Función polimórfica de clase: Función que toma como parámetro un tipo genérico pero que cumpla con una determinada clase. La función llama a una o más funciones nombradas en la clase, y por lo tanto para estar bien definida debe usarse sólo con tipos concretos que implementen la clase.

Sintaxis:

• Tipo enumerado:

      data <NombreTipo> = <Valor1> | ... | <ValorN>

• Clase:

      class <NombreClase> a where
          <funcion1> :: <aridad1>
          ...
          <funcionn> :: <aridadn>

• Instancia de clase en tipo:

      instance <Clase> <Tipo> where
          <definicion1>
          ...
          <definicionn>

Clase de una horita al final del práctico. Repasamos lo de la clase anterior y completamos con dos cosas.

Primero la definición polimórfica de lmax aprovechando la clase Ord:

lmax :: Ord a => [a] -> a
lmax [x] = x
lmax (x:y:xs) = max x (lmax (y:xs))

Y segundo el uso de “deriving” en la definición de un tipo, para pedirle a Haskell que instancie automáticamente para ese tipo algunas clases. Por ejemplo:

data Color = Red | Green | Blue deriving (Eq, Ord)

instancia automáticamente Eq y Ord para el tipo de datos Color sin que haga falta escribir el código que crea la instancia. En el caso de Ord, el orden que elige Haskell es el orden en el que se escribieron los valores. En el ejemplo visto, el orden sería Red < Green < Blue.

Primero repasamos lo visto el día anterior y vimos funcionando estas cosas en la computadora.

También vimos la clase Show y qué significa hacer “deriving” de esta clase (por ahora no explicado en este resumen).

Hasta ahora vimos sólo los tipos enumerados, que sólo permiten definir tipos finitos (por ejemplo Color tenía sólo 3 valores posibles). Ahora vamos a ver otra formas más interesantes de definir tipos.

Un tipo compuesto es un tipo cuyos valores tienen adentro (“estan compuestos por”) valores de otros tipos. Por ejemplo:

data Punto = Par Int Int deriving Show

(ejemplos de valores)…

Un tipo genérico es un tipo compuesto en el que no se especifican algunos de los tipos componentes. Por ejemplo:

data Point a b = P a b deriving Show

(ejemplos de valores)…

Un tipo recursivo es un tipo compuesto y/o genérico en donde uno o varios de los componentes son el mismo tipo que se está definiendo. Por ejemplo:

data MiLista a = Vacia | Pegar a (MiLista a) deriving Show

Observar que en este ejemplo el tipo “MiLista” aparece mencionando de nuevo (“recursivamente”) como uno de los componentes del tipo.

(ejemplos de valores)…

Otro ejemplo de tipo recursivo es:

data MiArbol a = Vacio | NoVacio a (MiArbol a) (MiArbol a)

En este caso el tipo “MiArbol” aparece mencionado no una sino dos veces como componente. Esto es lo que hace que los valores de este tipo puedan verse como árboles. En vez de hacer “deriving Show” del tipo MiArbol, instanciamos Show a mano para que los árboles se vean de una forma más linda:

instance Show a => Show (MiArbol a) where
    show Vacio = "."
    show (NoVacio x y z) = "( " ++ (show y) ++ " " ++ (show x) ++ " " ++ (show z) ++ " )"

Sintaxis:

• Tipos enumerados:

      data <NombreTipo> = <Valor1> | ... | <ValorN>

• Tipos compuestos:

data <NombreTipo> = <Constructor1> <Componente1> ... <ComponenteN> | ... | <ConstructorN> <Componente1> ... <ComponenteN>

Los nombres del tipo y de los constructores son los que uno quiera. Los componentes deben ser tipos previamente existentes.

• Tipos genéricos: sólo se agregan parámetros al esquema anterior. Los componentes ahora pueden ser estos parámetros.

data <NombreTipo> <param1> ... <paramN> = <igual que antes>

• Tipos recursivos: es un tipo compuesto o genérico en donde uno o varios de los componentes son el mismo tipo que se está definiendo.

Las funciones de alto orden son funciones que toman otras funciones como parámetros. En esta clase vimos dos funciones de alto orden muy útiles para hacer cosas con listas: map y foldr.

La función map toma una lista y una función. Aplica la función a los elementos de la lista devolviendo la lista resultante. Una forma general de ver su funcionamiento es con la siguiente expresión:

map f [x1, ..., xn] = [f x1, ..., f xn]

La función map ya viene definida en el preludio de Haskell pero si quisiéramos definirla por nosotros mismos podríamos hacerlo de la siguiente manera:

map :: (a -> b) -> [a] -> [b]
map f [] = []
map f (x:xs) = f x : map f xs

Un ejemplo de uso de map es para implementar la función inc que toma una lista de números y suma uno a cada elemento. La función inc se puede escribir sin usar map de la siguiente manera:

inc :: Num a => [a] -> [a]
inc [] = []
inc (x:xs) = (x+1) : inc xs

Usando map se puede definir así:

inc :: Num a => [a] -> [a]
inc xs = map f xs
  where f x = x+1

• Lectura recomendada: Tutorial de Haskell: 3 Funciones

Las expresiones lambda son expresiones que representan funciones. Estas funciones no tienen asignado un nombre. Sólo se especifican los parámetros que toman y el resultado que devuelven.

Un ejemplo de expresión lambda es

(\x -> x+1)

que representa una función que toma un parámetro x y devuelve x+1. Como es una función como cualquier otra, podemos preguntar el tipo de la función, y también podemos aplicarla sobre un parámetro para calcular el resultado:

Prelude> :t (\x -> x+1)
\x -> x + 1 :: Num a => a -> a
Prelude> (\x -> x+1) 44
45

También podemos pasarla como parámetro de una función de alto orden. Por ejemplo la función inc de la sección anterior se puede definir en una línea porque nos ahorramos tener que definir la función local f:

inc :: Num a => [a] -> [a]
inc xs = map (\x -> x+1) xs

Sintaxis general de una expresión lambda:

(\<param1> ... <paramN> -> <resultado>)

Primero vimos que todas las siguientes funciones tienen masomenos la misma estructura:

suma :: Num a => [a] -> a
suma [] = 0
suma (x:xs) = x + suma xs

paraTodo :: [Bool] -> Bool
paraTodo [] = True
paraTodo (x:xs) = x && paraTodo xs

concat :: [[a]] -> [a]
concat [] = []
concat (x:xs) = x ++ concat xs

suma calcula la suma de todos los elementos de una lista. paraTodo dice si todos los elementos de una lista son True. concat toma una lista de listas y devuelve la concatenación de todas las listas.

Todas estas funciones y muchas más tienen la misma estructura. Las únicas dos cosas que varían son el resultado del caso base (0, True ó []) y la operación que se aplica en la recursión (+, &&, ++). La función foldr captura la estructura en común y toma como parámetro las cosas que varían (el resultado del caso base y la operación). Una forma general de ver su funcionamiento es con la siguiente expresión ('o' es la operación, b es el resultado del caso base):

foldr o b [x1, ... , xn] = x1 'o' ( x2 'o' ... (xn 'o' b) ... )

Para que se entienda mejor lo vemos con una lista de largo 3:

foldr o b [x1, x2, x3] = x1 'o' ( x2 'o' (x3 'o' b) )

Las funciones anteriores se pueden definir usando foldr de la siguiente manera:

suma xs = foldr (+) 0 xs
paraTodo xs = foldr (&&) True xs
concat xs = foldr (++) [] xs

La función foldr se encuentra definida en el preludio de Haskell de la siguiente manera:

foldr            :: (a -> b -> b) -> b -> [a] -> b
foldr f z []      = z
foldr f z (x:xs)  = f x (foldr f z xs)

Hasta ahora las funciones que vimos usaron operaciones binarias sencillas como +, && y *. Pero las operaciones pueden ser mucho más complicadas dándole a foldr mucho más poder.

Por ejemplo vemos la función hayCero que toma una lista de números y devuelve un booleano que dice si hay algún cero en la lista. Sin foldr la función se puede definir así:

hayCero :: Num a => [a] -> Bool
hayCero [] = False
hayCero (x:xs) | x==0 = True
               | otherwise = hayCero xs

hayCero tiene la misma estructura que las otras funciones que vimos. Esto queda bien claro si reescribimos la definición de la siguiente manera:

hayCero :: Num a => [a] -> Bool
hayCero [] = False
hayCero (x:xs) = x `f` (hayCero xs)
  where f x y | x==0 = True                                                                   
              | otherwise = y                                                                 

O sea que hayCero se puede definir como foldr con caso base False y operación 'f':

hayCero xs = foldr f False xs
  where f x y | x==0 = True                                                                   
              | otherwise = y                                                                 

Usando expresiones lambda y quitando el xs a ambos lados, la definición quedaría así:

hayCero = foldr (\x y -> (x==0) || y) False