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 repetición sirve para ejecutar un bloque de código una y otra vez hasta que determinada condición o guarda se haga falsa. En general una repetición tiene la forma

while (<expr>) {
  <codigo>
}

a dónde <expr> es una expresión booleana y <codigo> es el bloque de código que queremos ejecutar repetidamente hasta que la guarda se haga falsa.

El siguiente código es un ejemplo de uso del while. Es una modificación del ejemplo de la sección anterior en el que se calculan cociente y resto de la división. El programa pide al usuario que ingrese dos números, pero esta vez pide repetidamente que ingrese el 2do número hasta que éste sea distinto de cero.

while.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);

  while (b == 0) {
    printf("Error: no puedo dividir por cero.\n");
    printf("Ingrese el divisor de nuevo: ");
    scanf("%i", &b);
  }

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

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

  return 0;
}

Las funciones sirven para separar un bloque de código que realiza una tarea determinada, de manera que pueda ser ejecutado varias veces con diferentes parámetros.

Las funciones tiene un nombre, una aridad y un cuerpo. La aridad es la cantidad y tipo de parámetros que toma, y el tipo de valor que devuelve como resultado. En general una función tiene la forma

<tipo_resultado> <nombre>(<parametros>) {
  
  <cuerpo>

  return <expr>;
}

a donde:

• <tipo_resultado> puede ser un tipo (“int”, “char”, etc.) o puede ser “void”, que quiere decir que la función no devuelve nada;
• <nombre> es el nombre que le queremos dar a la función;
• <parametros> es una secuencia de la forma <tipo1> <nombre1>, …, <tipon> <nombren>, que dice el tipo de cada parámetro y el nombre que le queremos dar;
• <cuerpo> es el bloque de código que ejecuta la función;
• “return <expr>” es la instrucción que indica el valor que devuelve la función (si <tipo_resultado> es “void”, esta instrucción no hace falta).

La función main del programa “Hola Mundo” es un claro ejemplo de función:

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

  return 0;
}

En este caso, la función no toma ningún parámetro y devuelve un valor de tipo int.

El siguiente código es otro ejemplo de uso de las funciones. Es una modificación del ejemplo de la sección anterior en el que se calculan cociente y resto de la división. En este caso, definiremos una función para el código que pide al usuario que ingrese un número, y la utilizaremos dos veces, una para el dividendo y otra para el divisor. Además, definiremos una función para el cálculo del cociente y el resto.

func.c

#include <stdio.h>

int leer_int(char* mensaje);
int dividir(int x, int y, int* z);

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

  a = leer_int("Ingrese el dividendo: ");
  b = leer_int("Ingrese el divisor: ");
  while (b == 0) {
    printf("Error: no puedo dividir por cero.\n");
    b = leer_int("Ingrese el divisor de nuevo: ");
  }

  q = dividir(a, b, &r);

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

  return 0;
}

int leer_int(char* mensaje) {
  int x;
  
  printf(mensaje);
  scanf("%i", &x);
  
  return x;
}

int dividir(int x, int y, int* z) {
  int w;
  
  w = x / y;
  *z = x % y;
  
  return w;
}

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;
  }
}

Falta completar. Ver los siguientes enlaces, tomados de "C Programming Reference". Está en inglés pero leyendo el código se puede llegar a entender.

• Tipos Básicos: http://www.space.unibe.ch/comp_doc/c_manual/C/CONCEPT/data_types.html.
• Enumeraciones: http://www.space.unibe.ch/comp_doc/c_manual/C/SYNTAX/enum.html.
• Estructuras: http://www.space.unibe.ch/comp_doc/c_manual/C/SYNTAX/struct.html.
• Definiciones de tipos: http://www.space.unibe.ch/comp_doc/c_manual/C/SYNTAX/typedef.html

arreglo.c

#include <stdio.h>

#define TAM 10

int main() {
  int arreglo[TAM], i;

  i = 0;
  while (i < TAM) {
    printf("Ingrese el %i-esimo valor: ", i);
    scanf("%i", &arreglo[i]);
    i = i + 1;
  }

  i = 0;
  while (i < TAM) {
    printf("%i\n", arreglo[i]);
    i = i + 1;
  }

  return 0;
}

booleano.h

typedef enum {False, True} booleano;

pila.h

#include "booleano.h"

#define LARGO_MAX 40

struct spila {
    int a[LARGO_MAX];
    int largo;
};

typedef struct spila pila;

pila pila_vacia();

booleano es_vacia(pila p);

pila push(pila p, int e);

pila pop(pila p);

int top(pila p);

pila.c

#include "pila.h"

pila pila_vacia() {
  pila p;
  p.largo = 0;
  return p;
}

booleano es_vacia(pila p) {
  booleano b;
  
  if (p.largo == 0) {
    b = True;
  } else {
    b = False;
  }
  return b;
}

pila push(pila p, int e) {
  p.a[p.largo] = e;
  p.largo = p.largo + 1;

pila pop(pila p) {
  p.largo = p.largo - 1;
  return p;
}

int top(pila p) {
  return p.a[p.largo-1];
}

Se compila con

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

main.c

#include <stdio.h>
#include "pila.h"

int main() {
  pila p1;
  
  p1 = pila_vacia();
  p1 = push(p1, 25);
  p1 = push(p1, 34);
  p1 = push(p1, 1);
  p1 = push(p1, 2);
  
  while (!es_vacia(p1)) {
    printf("El tope de la pila es %i\n", top(p1));
    p1 = pop(p1);
  }

  return 0;
}

Se compila el módulo main.o con

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

Se obtiene el ejecutable con

gcc main.o pila.o -o main

Los strings en C son simplemente arreglos de caracteres, con la única particularidad de que el final del string se marca con un caracter especial '\0'. De esta manera podemos tener en un arreglo de caracteres un string más corto que la cantidad de elementos del arreglo.

El siguiente código muestra cómo leer un string del teclado y guardarlo en un arreglo, y cómo recorrer los elementos del arreglo desde el principio hasta llegar al caracter '\0' que marca el final del string. Obsérvese que si el arreglo tiene TAM caracteres, entonces el string debe tener a lo sumo TAM-1 caracteres porque uno de los caracteres se va a usar para la marca '\0'.

strings.c

#include <stdio.h>

/* TAM es el tamanio maximo del string */
#define TAM 10

int main() {
  char str[TAM];
  int i;

  /* Leer un string del teclado: */
  printf("Ingrese el string (maximo %i caracteres): ", TAM-1);
  scanf("%s", str);

  /* Recorrer el string: */
  i = 0;
  while (str[i] != '\0') {
    printf("%i-esimo elemento: %c\n", i, str[i]);
    i = i + 1;
  }

  return 0;
}