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

El programa “Hola Mundo” es una forma típica de presentar un lenguaje de programación. Este programa muestra cómo hacer para imprimir en pantalla un mensaje que diga “Hola mundo!”.

hola.c:

#include <stdio.h>

int main() {
  printf("Hola mundo!\n");

  return 0;
}

El lenguaje C es un lenguaje compilado. Para usar los programas, primero hay que compilarlos usando un programa especial, el compilador que traduce el código en un archivo ejecutable. En esta materia vamos a usar el compilador GCC (GNU Compiler Collection), que se invoca a través del comando “gcc”. Para compilar el programa “hola.c” ejecutamos el siguiente comando:

gcc -Wall -pedantic -ansi hola.c -o hola

Las opciones “-Wall -pedantic -ansi” le indican al compilador que nos dé la mayor cantidad de advertencias y errores posibles sobre nuestro código. La opción “-o hola” le indica al compilador que el archivo ejecutable de salida debe llamarse “hola”. Para ejecutar el archivo hacemos:

./hola

Para interactuar con el usuario usaremos las funciones “printf” y “scanf” provistas por la librería “stdio.h”. Por ejemplo, el siguiente programa le pide al usuario que ingrese dos números, y luego imprime la suma de ambos:

es.c:

#include <stdio.h>

int main(void) {
  int a, b;

  printf("Ingrese los numeros a sumar:\n");

  scanf("%i", &a);
  scanf("%i", &b);

  printf("La suma da %i gracias por preguntar.\n", a + b);

  return 0;
}

La asignación sirve para guardar en una variable el resultado del cálculo de una expresión. En general una asignación tiene la forma

<var> = <expr>

a dónde <var> es una variable y <expr> es una expresión.

El condicional sirve para ejecutar un bloque de código sólo en caso de que se cumpla determinada condición o guarda. En general un condicional tiene la forma

if (<expr>) {
  <codigo>
}

a dónde <expr> es una expresión booleana y <codigo> es el bloque de código que queremos ejecutar en caso de que la guarda se cumpla. También existe una cláusula “else” que se ejecuta si la guarda es falsa:

if (<expr>) {
  <codigo>
} else {
  <codigo>
}

“if” y “else se pueden combinar para escribir un “if” multiguarda parecido a los análisis por caso de Haskell:

if (<expr>) {
  <codigo>
} else if (<expr>){
  <codigo>
...
} else {
  <codigo>
}

El siguiente código es un ejemplo de uso de la asignación y del if. El programa pide al usuario que ingrese dos números. Si el segundo número es cero, da un error. Si no, calcula el cociente y el resto de la división y guarda los resultados en las variables q y r, y luego imprime los resultados.

if.c:

#include <stdio.h>

int main(void) {
  int a, b, q, r;

  printf("Ingrese los numeros a dividir:\n");

  scanf("%i", &a);
  scanf("%i", &b);

  if (b == 0) {
    printf("Error: no puedo dividir por cero.\n");
    return 1;
  }

  q = a / b;
  r = a % b;

  printf("La division da %i con resto %i.\n", q, r);

  return 0;
}

La asignación múltiple

x1, ..., xn := E1, ..., En

se traduce a C como la secuencia de asignaciones simples

x1 = E1;
x2 = E2;
...
xn = En

Para garantizar que esta traducción es correcta, en cada expresión Ei sólo pueden aparecer variables xj con j >= i.

El condicional

if B0 -> S0
[] B1 -> S1
...
[] Bn -> Sn
fi

se traduce a C como

if (B0) {
  S0;
} else if (B1) {
  S1;
...
} else if (Bn) {
  Sn;
}

La repetición con una sola guarda

do B -> S od

se traduce a C como

while (B) {
  S;
}

La repetición multiguarda

do B0 -> S0
[] B1 -> S1
...
[] Bn -> Sn
od

se traduce primero a una repetición con una sola guarda con un if adentro

do B0 v B1 v ... v Bn ->
  if B0 -> S0
  [] B1 -> S1
  ...
  [] Bn -> Sn
  fi
od

y luego se traduce a C con las reglas ya vistas, obteniendo

while (B0 || B1 || ... || Bn) {
  if (B0) {
    S0;
  } else if (B1) {
    S1;
  ...
  } else if (Bn) {
    Sn;
  }
}