apunte haskell

Apunte Laboratorio ALPI *

Pablo Speciale

*Anlisis de Lenguaje de Programacin I - Universidad Nacional de Rosario

1

2 NDICE GENERAL

ndice1. Conceptos Importantes 4

1.1. Valores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41.2. Expresiones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41.3. Funciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41.4. Ecuaciones orientadas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51.5. Algunas definiciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51.6. Tipos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

2. Sintaxis de Haskell 72.1. Case sensitive . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72.2. Comentarios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72.3. Definiciones de Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72.4. Funciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

2.4.1. Identificadores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72.4.2. Operadores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82.4.3. Relacin entre identificadores y operadores . . . . . . . . . . . . . . . . . . . . 82.4.4. Definiciones de Funciones con Pattern Matching . . . . . . . . . . . . . . . . . 82.4.5. Definiciones con Guardas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92.4.6. Definiciones recursivas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92.4.7. Definiciones locales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92.4.8. Expresiones case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102.4.9. Aplicacin de Funciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

2.5. Secciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112.6. Tabla de precedencia/asociatividad de operadores . . . . . . . . . . . . . . . . . . . . . 112.7. Disposicin del cdigo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

3. Cosas sobre el Hugs 133.1. Prelude.hs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133.2. Iniciando Hugs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133.3. Comandos de Hugs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143.4. Un programa en Haskell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

4. Tipos de Haskell 164.1. Booleanos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

NDICE GENERAL 3

4.2. Nmeros enteros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174.3. Nmero en punto flotantes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174.4. Caracteres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184.5. Tipos de Funciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194.6. Listas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194.7. Cadenas (String) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204.8. Enumeraciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214.9. Tuplas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224.10. Polimorfismo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

5. Ms sobre funciones 245.1. Funciones annimas (lambda abstracciones) . . . . . . . . . . . . . . . . . . . . . . . . 245.2. Currificacin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

5.2.1. Forma prctica de ver la Currificacin . . . . . . . . . . . . . . . . . . . . . . . 275.3. Composicin de Funciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 275.4. Funciones totales y parciales. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

6. Evaluacin 296.1. Reduccin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 296.2. Evaluacin perezosa (o Lazy) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

4 1.4. ECUACIONES ORIENTADAS

1. Conceptos Importantes

En esta seccin se explica que es un lenguaje funcional puro. Adems, se dan algunas definicionesque son la esencia de Haskell.

1.1. Valores

Entidades matemticas abstractas con ciertas propiedades. Una expresin denota un valor. Entre lasclases de valores que una expresin puede denotar, se incluyen: nmeros de varios tipos (Int, Integer,Float, etc.), caracteres, funciones y listas. Observar que, en Haskell, las funciones tambin son valores.

1.2. Expresiones

Cadenas de smbolos utilizados para denotar valores

Expresiones atmicas: llamadas tambin formas normales. Por abuso de notacin, les decimosvalores.

Expresiones compuestas: se arman combinado subexpresiones. Por abuso de notacin, slo lesdecimos expresiones.

Notas

1. No confundir entre valores y su representacin (mediante expresiones). Pueden existir muchas for-mas de representar un mismo valor. Por ejemplo, 5 101 (en binario) V (en nmeros Romanos).

2. Una expresin est bien formada si cumple con las reglas sintcticas y reglas de asignacin detipo.

3. Algunos valores no tienen representacin cannica, por ejemplo, los valores funcionales.

1.3. Funciones

Visin denotacional: una funcin es un valor matemtico que relaciona cada elemento de un con-junto (de partida) con un nico elemento de otro conjunto (de llegada).

Visin operacional: una funcin es un mecanismo que dado un elemento del conjunto de partida,calcula el elemento correspondiente del conjunto de llegada.

Extensionalidad

Este principio recibe el nombre de principio de extensionalidad.

f = g f x = g x

1. CONCEPTOS IMPORTANTES 5

1.4. Ecuaciones orientadas

Expresion a definir = Expresion definidae1 = e2

Visin denotacional: se define que el valor denotado por e1 es el mismo que el denotado por e2.

Visin operacional: para calcular el valor de una expresin que contiene a e1, se puede reemplazare1 por e2.

Nota

Dada una expresin bien formada, determinamos el valor que denota mediante ecuaciones. Y cal-culamos el valor de la misma, reemplazando subexpresiones, de acuerdo con las reglas dadas por lasecuaciones, a sto se lo llama reduccin (ver seccin 6).

1.5. Algunas definiciones

Funcin de alto orden: una funcin que recibe otra funcin como argumento, o la retorna como resul-tado.

Transparencia Referencial: el valor de una expresin depende slo de los elementos que la constituyen.Una definicin ms informal, cuando dos cosas son iguales que sean iguales en todas partes. Por ejemplo,en C, uno puede hacer lo siguiente:

x = x + 1;

Se le asigna a x el valor de x+1. Este ejemplo muestra un lenguaje que no posee la importante propiedadde Transparencia Referencial, pues x no vale lo mismo antes y despus de la asignacin. Un lenguajeas se dice que posee Efectos colaterales.La Transparencia Referencial implica:

Abstraccin de detalles de ejecucin. Posibilidad de demostrar propiedades usando las propiedades de las subexpresiones y mtodos de

deduccin lgicos.

Lenguaje funcional puro: lenguaje de expresiones con transparencia referencial y funciones de alto or-den, cuyo modelo de cmputo es la reduccin realizada mediante el reemplazo de igualdad por igualdad.Haskell es un lenguaje funcional puro.

6 1.6. TIPOS

1.6. Tipos

Conjunto de valores con propiedades comunes. Los tipos denotan conjuntos de valores.

Tipado Fuerte (strong typing): toda expresin debe tener un tipo para ser vlida.Notacin: e :: A se lee la expresin e tiene tipo A.Significa el valor denotado por e pertenece al conjunto de valores denotado por A.

Inferencia de tipos:Dada un expresin e, determinar si tiene tipo o no segn las reglas, y cul es ese tipo 1.Algunas reglas de inferencia de tipo:

si e1 :: A y e2 :: B (e1, e2) :: (A,B)si m,n :: Int m + n :: Intsi d = e y e :: A d :: A

Chequeo de tipos: (e,A) BoolDada una expresin e y un tipo A, determinar si e :: A segn las reglas.

1Devuelve el tipo ms general, es decir, el tipo con ms variables de tipos

2. SINTAXIS DE HASKELL 7

2. Sintaxis de Haskell

En esta seccin se muestra lo esencial de la sintaxis de Haskell.

2.1. Case sensitive

La sintaxis de Haskell diferencia entre maysculas y minsculas. Se dice que es Case sensitive.

2.2. Comentarios

Los comentarios empiezan con -- (dos menos). Por ejemplo:-- Este es un comentario, cuando empieza con "--"-- Haskell (ms precisamente Hugs o ghc) lo ignora

2.3. Definiciones de Variables

La definicin de una variable tendr la forma

nombre_variable :: Tiponombre_variable = expresion

como en el ejemplosize :: Integersize = 12 + 13

2.4. Funciones

Existen dos formas de nombrar una funcin, mediante un identificador (por ejemplo, sum, producty fact), o mediante un smbolo de operador (por ejemplo, * y +)

2.4.1. Identificadores

Los identificadores de variables o funciones deben comenzar con una letra minscula, seguido, op-cionalmente por una secuencia de caracteres, cada uno de los cuales es: una letra, un dgito, un apstrofe() o un guin bajo (_). Los siguientes son ejemplos posibles de identificadores:

sum f f fintSum nombre_con_guiones

Los siguientes identificadores son palabras reservadas y no pueden utilizarse como nombres de fun-ciones o variables:

case of where let in ifthen else data type infix infixlinfixr class instance primitive

8 2.4. FUNCIONES

2.4.2. Operadores

Algunas funciones se escriben entre sus (dos) argumentos en lugar de precederlos. A una funcinescrita usando la notacin infija se le llama un operador. Por ejemplo,

3 ? @ \ ^ | -

Leer seccin 1.4.3 del libro.

2.4.3. Relacin entre identificadores y operadores

Se proporcionan dos mecanismos simples para utilizar un identificador como un smbolo de operadoro un smbolo de operador como un identificador:

Cualquier identificador ser tratado como un smbolo de operador si est encerrado entre comillasinversas (). Por ejemplo,

x mod y es equivalente a mod x y

Cualquier smbolo de operador puede ser tratado como un identificador encerrndolo en parntesis.Por ejemplo,

x + y es equivalente a (+) x y

2.4.4. Definiciones de Funciones con Pattern Matching

La declaracin de una funcin f est formada por un conjunto de ecuaciones con el formato:f . . . =

Donde cada una de las expresiones < pat1 >< pat2 > ... < patn > representa un argumento2 de lafuncin y es denominado un patrn. El nmero n de argumentos se denomina aridad. Si f fuese definidapor ms de una ecuacin, cada una debe tener la misma aridad.

Si f fuese un operador sera:

f =

Por ejemplo,minimo :: (Integer, Integer) -> Integerminimo (x,y) = if x Integerfact 0 = 1fact (n+1) = (n+1) * fact n

Observar que se us 0 y n+1 para que los patrones sean disjuntos. Al a ser los patrones disjuntos, elorden en que aparecen las ecuaciones no importa; en caso contrario, s es importante el orden.Leer seccin 1.5.1 del libro.

2.4.7. Definiciones locales

Considrese la siguiente funcin que calcula el nmero de races diferentes de una ecuacin cuadr-tica de la forma ax2 + b x + c = 0

numeroDeRaices :: Int -> Int -> Int -> IntnumeroDeRaices a b c

10 2.5. SECCIONES

| discr > 0 = 2| discr == 0 = 1| discr < 0 = 0where discr = b*b - 4*a*c

Las definiciones locales pueden tambin ser introducidas por let de la forma:

let in


2.4.8. Expresiones case

Una expresin case puede ser utilizada para evaluar una expresin y, dependiendo del resultado,devolver uno de los posibles valores.

paridad :: Int -> Stringparidad x = case (x mod 2) of

0 -> "par"1 -> "impar"

2.4.9. Aplicacin de Funciones

Notar que en la aplicacin de una funcin, los argumentos no necesitan ser encerrados entre parntesis(cmo usualmente se hace en matemticas). Supngase la siguientes

promedio :: Float -> Float -> Floatpromedio a b = (a+b)/2

Por ejemplo, si queremos calcular el promedio entre 5 y 47, podemos hacer en hugs (ver seccin 3):

Hugs> promedio 5 4726.0

Los parntesis van a ser necesarios cuando queramos romper el orden de precedencia estndar de losoperadores. Como la aplicacin de funcin tiene precedencia ms alta que todos los dems operadores,si queremos calcular el promedio ente 6 y 9+9, tenemos que hacer

Hugs> promedio 6 (9+9)12.0

Pues,

promedio 6 9 + 9 equivale a (promedio 6 9) + 9

2. SINTAXIS DE HASKELL 11

2.5. Secciones

Se puede encerrar tambin un argumento junto con el operador.(x) y = x y( y) x = x y

Una excepcin: (x) se interpreta como la aplicacin del operador unario de negacin.Leer seccin 1.4.4 del libro.

2.6. Tabla de precedencia/asociatividad de operadores

infixl 9 !!infixr 9 .infixr 8 ^infixl 7 *infix 7 /, div, rem, modinfixl 6 +, -infix 5 \\infixr 5 ++, :infix 4 ==, /=, infix 4 elem, notEleminfixr 3 &&infixr 2 ||

Observaciones

La aplicacin de funciones tiene la mayor precedencia. A B C significa A (B C)

Leer seccin 1.4.5 y 1.4.6 del libro.

2.7. Disposicin del cdigo

Cmo es posible evitar la utilizacin de separadores que marquen el final de una ecuacin, unadeclaracin, etc. Por ejemplo, dada la siguiente expresin:

ejemplo x y z = a + bwhere a = f x y

b = g z

Cmo sabe el sistema Haskell que no debe analizarla como:

ejemplo x y z = a + bwhere a = f x

y b = g z

12 2.7. DISPOSICIN DEL CDIGO

La respuesta es que el Haskell utiliza una sintaxis bidimensional denominada espaciado (layout) quese basa esencialmente en que las declaraciones estn alineadas por columnas. En el ejemplo anterior,obsrvese que a y b comenzaban en la misma columna. Las reglas del espaciado son bastante intuitivasy podran resumirse en:

1. El siguiente carcter de cualquiera de las palabras clave where, let u of es el que determina lacolumna de comienzo de declaraciones en las expresiones where, let o case correspondien-tes. Por tanto podemos comenzar las declaraciones en la misma lnea que la palabra clave, en lasiguiente o siguientes.

2. Es necesario asegurarse que la columna de comienzo dentro de una declaracin est ms a la de-recha que la columna de comienzo de la siguiente clusula. En caso contrario, habra ambigedad,ya que el final de una declaracin ocurre cuando se encuentra algo a la izquierda de la columna decomienzo.

El espaciado es una forma sencilla de agrupamiento que puede resultar bastante til. Por ejemplo, ladeclaracin anterior sera equivalente a:

ejemplo x y z = a + bwhere { a = f x y ;

b = g z }

3. COSAS SOBRE EL HUGS 13

3. Cosas sobre el Hugs

Existen varias implementaciones de Haskell; nosotros usaremos Hugs, ya que es libre, est disponi-bles para distintas plataformas (MS-Windows, Mac OS X, Unix), presenta una interfaz de usuario flexibley es bastante eficiente.

3.1. Prelude.hs

El prelude es un fichero de nombre Prelude.hs que es cargado automticamente al arrancar Hugsy contiene la definicin de un conjunto de funciones que podemos usar cuando las necesitemos. Algunosejemplos: div, mod, sqrt, id, fst, snd.

3.2. Iniciando Hugs

Al iniciar una sesin en Hugs, nos aparecer una ventana como sta:

__ __ __ __ ____ ___ _________________________________________

|| || || || || || ||__ Hugs 98: Based on the Haskell 98 standard||___|| ||__|| ||__|| __|| Copyright (c) 1994-2005||---|| ___|| World Wide Web: http://haskell.org/hugs|| || Report bugs to: [email protected]|| || Version: May 2006 _________________________________________Haskell 98 mode: Restart with command line option -98 to enable extensions

Type :? for helpHugs>

Hugs evaluar cualquier expresin, sintcticamente correcta, que se ingrese en el prompt

Hugs>

Por ejemplo, si ingresemos (7 + 4) 3, la evaluar y nos devolver 33

Hugs> (7+4)*333

Si ingresamos sqrt 2, nos devolver una aproximacin de

2

Hugs> sqrt 21.4142135623731

14 3.4. UN PROGRAMA EN HASKELL

3.3. Comandos de Hugs

Si uno escribe :? y presiona ENTER:

LIST OF COMMANDS: Any command may be abbreviated to :c wherec is the first character in the full name.

:load load modules from specified files:load clear all files except prelude:also read additional modules:reload repeat last load command:project use project file:edit edit file:edit edit last module:module set module for evaluating expressions evaluate expression:type print type of expression:? display this list of commands:set set command line options:set help on command line options:names [pat] list names currently in scope:info describe named objects:browse browse names defined in :find edit module containing definition of name:!command shell escape:cd dir change directory:gc force garbage collection:version print Hugs version:quit exit Hugs interpreter

La primer lnea dice que se puede usar como abreviatura slo la primera letra de cada comando. Observarestos comandos equivalentes:

Hugs> :type idid :: a -> aHugs> :t idid :: a -> aHugs>

El comando :t imprime el tipo de una expresin.

3.4. Un programa en Haskell

Por ahora hemos evaluado expresiones en el prompt de Hugs y escrito algunas definiciones. Pero,dnde guardamos esas definiciones? cmo hacemos para usarlas? En esta seccin responderemostodas estas cuestiones.

3. COSAS SOBRE EL HUGS 15

A una lista de definiciones se la denomina script. Los pasos a seguir para resolver un problema seranlos siguientes:

1. Escribimos un script con la definicin de todas las funciones que necesitemos para resolver el pro-blema. Para ello podemos utilizar cualquier editor de texto, aunque es recomendable usar algunoque resalte automticamente la sintaxis de Haskell. Guardamos el archivo con una extensin .hs.

2. Cargamos el script en Hugs. Para ello utilizamos el comando :load seguido del nombre del archi-vo. Ahora en el prompt de Hugs ya podemos evaluar cualquier expresin que haga referencia afunciones definidas en el script.

Al escribir el script debemos recordar que Haskell distingue entre maysculas y minsculas (se diceque es Case Sensitive. Por ejemplo, mi_funcion y mi_Funcion resultan identificadores distintos.

Una buena prctica de programacin es documentar siempre el cdigo fuente. Un comentario en unscript es informacin de valor para el lector humano, ms que para el computador (no interviene paranada al momento de evaluar una expresin). El smbolo -- inicia un comentario, que ocupa la partede la linea hacia la derecha del smbolo.

16 4.2. NMEROS ENTEROS

4. Tipos de Haskell

Se introduce algunos tipos de datos bsicos (Booleanos, Char, Int) y tipos de datos compuestos (tu-plas, listas, funciones).

Para qu sirven los tipos?

Deteccin de errores comunes Documentacin Especificacin rudimentaria Oportunidad de optimizacin en compilacin

Importante: es una buena prctica en programacin empezar dando el tipo del programa que se quiereescribir.

Leer el captulo 2 del libro

4.1. Booleanos

Se representan por el tipo Bool y contienen dos valores: False y True. El tipo de datos Bool sepuede definir con una declaracin de tipos de datos:

data Bool = False | TrueEl prelude incluye varias funciones para manipular valores booleanos:

Sintaxis de Haskell Sintaxis estndar en lgica

x && y x yx || y x ynot x xx == y x yx /= y x 6 y o x xor y

Haskell tambien incluye una construccin que permite seleccionar entre dos alternativas dependiendode un valor booleano.

if condicion then expresion1 else expresion2funciona de la siguiente manera: se evala condicion; si reduce a True (i.e. la condicin es verdadera)se evalua expresion1 y se devuelve su valor, y si reduce a False (i.e. la condicin es falsa), se evalua ydevuelve el valor de expresion2.

Obsrvese que una expresin de ese tipo slo es aceptable si condicion es de tipo Bool y siexpresion1 y expresion2 son del mismo tipo.

Leer seccin 2.1 del libro.

4. TIPOS DE HASKELL 17

4.2. Nmeros enteros

Existen dos tipos bsicos para representar enteros: Int e Integer. Ambos incluyen los enterosnegativos, el cero y los enteros positivos. La nica diferencia es que Int representa enteros de rangoacotado, mientras que Integer representa enteros de rango arbitrario.

Esto significa que operar con valores de tipo Int puede provocar un desbordamiento, y el resultadopuede no ser el correcto. En cambio, la aritmtica Integer no presenta este inconveniente. Notar queeste beneficio se gana a costo de algo de prdida de performance: la aritmtica Integer es ms lentaque la aritmtica Int.

En el prelude se incluye un amplio conjunto de operadores y funciones que manipulan enteros:

(+) suma.(*) multiplicacin.(-) substraccin.(^) potenciacin.negate menos unario (la expresin "-x" se toma como "negate x")div divisin enterarem/mod resto de la divisin entera. Siguiendo la ley:

(x div y)*y + (x rem y) == xmdulo, como rem slo que el resultado tiene el mismosigno que el divisor.

odd devuelve True si el argumento es impareven devuelve True si el argumento es par.abs valor absolutosignum devuelve -1, 0 o 1 si el argumento es negativo, cero

positivo, respectivamente.

Ejemplos3^4 == 81, 7 div 3 == 2, even 23 == False7 rem 3 == 1, -7 rem 3 == -1, 7 rem -3 == 1

4.3. Nmero en punto flotantes

En ciencias de la computacin, a los nmeros con parte fraccionaria, se los denomina nmeros enpunto flotante. En Haskell, stos estan provistos por los tipos bsicos Float y Double.

Tener en cuenta que estos valores son aproximaciones que se representan con un nmero fijo dedgitos, y que bajo ciertas circunstancias esto puede provocar errores de redondeo.

Los nmeros pueden describirse con la notacin decimal estndar, o utilizando notacin cientfica;por ejemplo, 1.0e3 equivale a 1000.0, mientras que 5.0e-2 equivale a 0.05.

Otro uso corriente de los nmeros en punto flotante es para representar enteros que son demasiadograndes en valor absoluto para declararse como Int, pero que tienen pocos dgitos significativos, porejemplo 56.23e12.

18 4.4. CARACTERES

La diferencia entre Float y Double reside en que los primeros representan nmeros en puntoflotante de precisin simple, mientras que los segundos, nmeros en punto flotante de precisin doble.

El prelude incluye tambin mltiples funciones de manipulacin de flotantes:

(+), (-), (*), (/) Suma, resta, multiplicacin ydivisin fraccionaria.

(^) Exponenciacin con exponente entero.(**) Exponenciacin con exponente fraccionario.sin, cos, tan Seno, coseno y tangente.asin, acos, atan Arcoseno, arcocoseno y arcotangente.ceiling Convierte un nmero fraccionario en un

entero redondeando hacia el infinito.floor Convierte un nmero fraccionario en un

entero redondeando hacia el menos infinito.truncate Convierte un nmero fraccionario en un entero

redondeando hacia el cero (trunca laparte decimal).

round Convierte un nmero fraccionario en un enteroredondeando hacia el entero ms cercano.

fromIntegral Convierte un entero en un nmero enpunto flotante.

log Logaritmo en base e.sqrt Raz cuadrada (positiva).

4.4. Caracteres

Representados por el tipo Char, los elementos de este tipo representan caracteres individuales comolos que se pueden introducir por teclado. Los valores de tipo carcter se escriben encerrando el valorentre comillas simples, por ejemplo

a, 0, ., y Z

Notar que 0 y 0 son dos valores distintos. El primero es de tipo caracter y el segundo de tipoentero.

Algunos caracteres especiales deben ser introducidos utilizando un cdigo de escape; cada uno destos comienza con el carcter de barra invertida (\) , seguido de uno o ms caracteres que seleccionanel carcter requerido. Algunos de los ms comunes cdigos de escape son:

\\ barra invertida\ comilla simple\" comilla doble\n salto de lnea

En contraste con algunos lenguajes comunes (como el C, por ejemplo), los valores de tipo Char soncompletamente distintos de los enteros. Sin embargo, el prelude proporciona dos funciones primitivas,ord y chr, que permiten realizar la conversin.


ord :: Char -> Intchr :: Int -> Char

Por ejemplo, la siguiente funcin convierte maysculas en minsculas.

mayusc :: Char -> Charmayusc c = chr (ord c - ord a + ord A)


4.5. Tipos de Funciones

Si a y b son dos tipos, entonces a b es el tipo de una funcin que toma como argumento unelemento de tipo a y devuelve un valor de tipo b. Las funciones en Haskell son objetos de primeraclase. Pueden ser argumentos o resultados de otras funciones o ser componentes de estructuras de datos.Esto permite simular mediante funciones de un nico argumento, funciones con mltiples argumentos.Considrese, por ejemplo, la funcin de suma (+). En matemticas se toma la suma como una funcinque toma una pareja de enteros y devuelve un entero. Sin embargo, en Haskell, la funcin suma tiene eltipo:

(+) :: Int -> (Int -> Int)

(+) es una funcin de un argumento de tipo Int que devuelve una funcin de tipo Int Int. Dehecho (+) 5 denota una funcin que toma un entero y devuelve dicho entero ms 5. Este proceso sedenomina currificacin y permite reducir el nmero de parntesis necesarios para escribir expresiones.De hecho, no es necesario escribir f(x) para denotar la aplicacin de la funcin f al argumento x, sinosimplemente f x. Ver ms sobre currificacin en la seccin 5.2.Leer sobre currificacin en seccin 1.4.2 del libro.

Cul es la operacin bsica de una funcin?La Aplicacin a un elemento de su partida. La Aplicacin es la operacin con mayor precedencia.

Qu expresiones denotan funciones? Nombres definidos como funciones: Ej.: cuadrado Funciones Annimas3 (lambda abstracciones). Ej.: (\ x x + x) Resultado de usar otras funciones. Ej.: cuadrado . cuadrado

4.6. Listas

Si a es un tipo cualquiera, entonces [a] representa el tipo de listas cuyos elementos son valores detipo a. Por ejemplo,

3Ver ms sobre Funciones Annimas en 5.1

20 4.7. CADENAS (STRING)

xs :: [Int]xs = [1, 8, 2, 4]

El prelude incluye un amplio conjunto de funciones de manejo de listas, por ejemplo:

length xs devuelve el nmero de elementos de xsxs ++ ys devuelve la lista resultante de concatenar

xs e ysconcat xss devuelve la lista resultante de concatenar

las listas de xssmap f xs devuelve la lista de valores obtenidos al aplicar

la funcin f a cada uno de los elementos de lalista xs.

Convenio: para representar una lista se usa el convenio xs, para listas de listas se usa xss, y as suce-sivamente.

Luego, volveremos con las Listas.

4.7. Cadenas (String)Una cadena es tratada como una lista de caracteres y el tipo String se toma como una abreviacin

de [Char]. El tipo String es un renombramiento:

type String = [Char]

Las cadenas pueden ser escritas como secuencias de caracteres encerradas entre comillas dobles. Todoslos cdigos de escape utilizados para los caracteres, pueden utilizarse para las cadenas.

Hugs> "hola""hola"

Hugs> [h,o,l,a]"hola"

Hugs>

Puesto que las cadenas son representadas como listas de caracteres, todas las funciones para listaspueden ser utilizadas tambin con cadenas:

Hugs> length "Hola"4

Hugs> "Hola, " ++ "amigo""Hola, amigo"


Hugs> concat ["Esto"," ","es"," ","una"," ", "cadena"]"Esto es una cadena"

Hugs> map ord "Hola"[104, 111, 108, 97]

Hugs>

La diferencia entre a y a es que lo primero es un carcter, mientras que lo segundo es una lista decaracteres que contiene un nico elemento.Leer seccin 2.7 del libro.

4.8. Enumeraciones

Un modo de definir un nuevo tipo de datos es enumerar explcitamente sus valores. Por ejemplo,data Dia = Dom | Lun | Mar | Mie | Jue | Vie | Sab

Los nombres de las constructoras se distinguen de otras clases de nombres hacindolos comenzar poruna letra mayscula. El nombre de un tipo declarado, tambin comienza por una letra mayscula.

El tipo Dia define un conjunto de siete valores distintos. Cada uno de estos valores se dice qie es uncontructores del tipo Dia.

Por defecto, esta definicin no me permite operar con valores de tipo Dia en la manera que esperaria:no puedo comparar dos valores por igualdad, no puedo imprimir sus valores en pantalla, etc.

Para poder hacer esto, debo agregarle a la defincin una opcin ms:

data Dia = Dom | Lun | Mar | Mie | Jue | Vie | Sabderiving(Eq, Ord, Enum, Show)

que hace que se genere automticamente las declaraciones de las instancias de las clases de tipos nom-bradas.

Si a es el tipo siendo definido,

Eq: permite usar los operadores == y /= con valores de tipo a, Ord: permite usar los operadores = con valores de tipo a. La relacin Int y toEnum :: Int -> a. La fun-cin fromEnum asocia un natural a cada uno de los valores de a, de acuerdo al orden en ladeclaracin y comenzando con 0. toEnum es la inversa a izquierda de fromEnum. Por ejemplofromEnum Dom reduce a 0, fromEnum Mie reduce a 3 y toEnum 2 == Mar4 reduce aTrue.

4No se puede inferir el tipo de toEnum 2.

22 4.10. POLIMORFISMO

Show: permite imprimir los valores del tipo a en pantalla.


4.9. Tuplas

Un modo de combinar tipos para crear tipos nuevos es construir pares. El tipo (A,B) corresponde ala operacin de producto cartesiano de la teora de conjuntos.

Contamos con los destructores fst y snd que devuelve la primer y segunda componente de un parrespectivamente; por ejemplo fst (2,b) reduce a 2 y snd (2,b) reduce a b.

Ms general, si T1, T2, ..., Tn son tipos y n 2, entonces hay un tipo de n-tuplas escrito (T1, T2, ..., Tn)cuyos elementos pueden ser escritos como (x1, x2, ..., xn) donde cada x1, x2, ..., xn tiene tipos T1, T2, ..., Tnrespectivamente.

Ejemplo

(1, [2], 3) :: (Int, [Int], Int)(a, False) :: (Char, Bool)((1,2),(3,4)) :: ((Int, Int), (Int, Int))

Obsrvese que, a diferencia de las listas, los elementos de una tupla pueden tener tipos diferentes. Sinembargo, el tamao de una tupla es fijo.

Por completitud, Haskell tambin proporciona una tupla vaca. Por definicin, la expresin (), ledaunit, tiene tipo (). El tipo () tiene dos elementos, y (). Un uso posible de () es convertir las constantesen funciones; por ejemplo,

pifun :: () -> Floatpifun = 3.14159

Al elevar las constantes al nivel de las funciones, se puede ir ms all en el estilo de programacin noaplicativo. Por ejemplo, se podra escribir

cuadrado . cuadrado . pifun en lugar de (cuadrado . cuadrado) piLeer seccin 2.4 del libro.

4.10. Polimorfismo

Algunas funciones y operadores trabajan con muchos tipos. Por ejemplo,

id :: a -> aid x = x

Se lee id es una funcin que dado un elemento de algn tipo a, retorna un elemento de ese mismo tipo.Aqu a denota variables de tipo. Un tipo que contenga variables de tipo se denomina tipo polimrfico.


Entonces, la identidad es una funcin polimrfica. El tipo de su argumento puede ser instanciado. Porejemplo,

(id 3) :: Int y aqu id :: Int -> Int(id True) :: Bool y aqu id :: Bool -> Bool


24 5.2. CURRIFICACIN

5. Ms sobre funciones

Aqu se explica que es currificacin, y se da diferentes formas de construir funciones.

5.1. Funciones annimas (lambda abstracciones)Una expresin que denota una funcin son las lambda abstracciones:

x . x + x

var . expresion

var: es el binder. La variable de cuantificacin o ligador.

expresion: es el scope. El alcance de la variable de cuantificacin.

En Haskell se escriben as

\ x -> x + x

El significado es el siguiente:

(\ x E) x0 E [x := x0]Por ejemplo,

(\x -> x + x) 2= < Por regla anterior >

(x + x) [ x := 2 ]= < Sustitucin >

2 + 2= < Aritmtica >

4

Veamos dos formas equivalentes de definir una misma funcin:

doble x = x + xdoble = \ x x + x

5.2. Currificacin

Un artificio til para reducir el nmero de parntesis de una expresin consiste en reemplazar un argu-mento estructurado por una secuencia de argumentos ms simples. Para ilustrar esta idea, consideremosla funcin suma.

suma :: (Integer,Integer) -> Integersuma (x,y) = x + y

5. MS SOBRE FUNCIONES 25

Otra definicin, esencialmente equivalente, de la misma funcin es:

sumac :: Integer -> Integer -> Integersumac x y = x + y

Veamos antes algo sobre funciones annimas.

(\y -> y + 1) 8= < def. de lambda expresiones >

(y + 1) [ y := 8 ]= < Sustitucin >


9

Esto es la funcin sucesor, definida comnmente como:

succ :: Integer -> Integersucc y = y + 1

O sea,

succ = \y -> y + 1

Y la expresin anterior queda

(\y -> y + 1) 8= < def. de succ >

succ 8= < def. de succ >

9

Si quisiramos generalizar an ms la funcin anterior y en vez de sumar 1 se suma un x genrico. Parael ejemplo siguiente, la funcin (annima) recibe dos argumentos (uno despus del otro); en este caso,12 y luego 89, y se intentar sumarlos.

(\x -> (\y -> x + y)) 12 89= < def. de lambda expresiones >

((\y -> x + y) 89) [x := 12]= < Sustitucin >

(\y -> 12 + y) 89= < def. de lambda expresiones >

(12 + y) [ y := 89 ]= < Sustitucin >


101

26 5.2. CURRIFICACIN

Observe aqu que la funcin annima se comporta como lo hara sumac. Veamos qu es lo que sucede:

sumac = \ x (\ y x + y)sumac x = \ y x + ysumac x y = x + y

Para que la currificacin funcione de un modo consistente, necesitamos que la operacin de aplicacinfuncional asocie a la izquierda en las expresiones. As,

sumac x y significa (suma x) ycuadrado cuadrado x significa (cuadrado cuadrado) x

Observar que la ltima es incorrecta. Tambin observar que el operador asocia a la derecha. Esto es:

A B C significa A (B C)

Ver en la tabla de asociatividad en la seccin 2.6.La currificacin conlleva dos ventajas. En primer lugar, puede ayudar a reducir el nmero de parn-

tesis que han de escribirse en las expresiones. En segundo lugar, las funciones currificadas pueden seraplicadas a un solo argumento, dando como resultado otra funcin que puede ser til por s misma. Porejemplo,

suma 1 = succ

Demostraremos sto, primero recordar

sumac x

= < Una de las def. de sumac >\y -> x + y

Instanciando el x a 1

sumac 1= < Def. de sumac >

\y -> 1 + y= < Conmunt. >

\y -> y + 1= < Def. de succ >

succ

Si lo deseamos, siempre podemos convertir una funcin no currificada en otra currificada. La funcincurry toma un funcin no currificada y devuelve un versin currificada de la misma funcin; su definicines

curry :: ((a,b) -> c) -> a -> b -> ccurry f x y = f (x,y)

5. MS SOBRE FUNCIONES 27

La funcin uncurry hace lo opuesto y convierte una funcin currificada en otra que no lo es.

uncurry :: (a -> b -> c) -> (a,b) -> cuncurry f (x,y) = f x y


5.2.1. Forma prctica de ver la Currificacin

Para fines prctico, slo es necesario pensar que la funciones toman una secuencia de argumentos ydevuelve un resultado. Por ejemplo,

suma4 :: Int -> Int -> Int -> Int -> Intsuma4 x1 x2 x3 x4 = x1 + x2 + x3 + x4

Aunque nos quedamos con sta idea intuitiva de currificacin, es didctico ver cmo queda poniendotodos los parntesis.

suma4 :: Int -> (Int -> (Int -> (Int -> Int)))(((suma4 x1) x2) x3) x4 = x1 + x2 + x3 + x4

Nos quedamos con la primera definicin de suma4.

5.3. Composicin de Funciones

La composicin de dos funciones f y g se define mediante la ecuacin

(.) :: (b -> c) -> (a -> b) -> a -> c(f . g) x = f (g x)

La funcin (f . g) aplicada a x se define como el resultado de aplicar primero g a x, y luego aplicaral resultado f.

Recordar la Relacin entre identificadores y operadores (ver 2.4.3). Por dicha relacin, una defini-cin alternativa sera,

(.) :: (a -> b) -> (c -> a) -> c -> b(.) f g x = f (g x)

Pero nos quedaremos con la primera.La composicin funcional es una operacin asociativa.

(f . g) . h = f . (g . h)

para todas las funciones f, g y h de tipos apropiados. En consecuencia, no hay necesidad de ponerparntesis al escribir secuencias de composiciones.Leer seccin 1.4.7 del libro.

28 5.4. FUNCIONES TOTALES Y PARCIALES.

5.4. Funciones totales y parciales.

Decimos que una funcin es total, si est definida para todo elemento de su dominio. En otras pala-bras, f :: A -> B es total si y slo si f x 6= para todo x::A. En caso contrario, decimos quef es parcial. Ver la definicin de Botton () en la seccin 6.1.

Por ejemplo, si definimos

double :: Integer -> Integerdouble x = 2 * x

fact :: Integer -> Integerfact n = if n==0 then 1 else n * fact(n-1)

reciproco :: Float -> Floatreciproco x = 1/x

double resulta una funcin total, mientras que fact y reciproco resultan parciales. Esto sedebe a que fact aplicado a un entero negativo denota una computacin que no termina, y reciprocono est definido en cero.

Notar que en programacin funcional tenemos una definicin diferente de dominio de una funcin ala que tenemos usualmente en matemticas. En matemticas escribimos f : A B para denotar que fes una funcin definida para todo x en A, mientras que en Haskell, f :: A -> B significa que f estdefinida (i.e. no evala a ) para eventualmente alguno de los valores en A.

6. EVALUACIN 29

6. Evaluacin

6.1. Reduccin

Definicin: cero o ms contracciones (reemplazo de un redex).

Redex (reducible expresin): subexpresin que coincide con una instancia del lado izquierdo de unecuacin. Un redex ms interno es aquel que no contiene otro redex. Un redex ms externo es aquel queno est contenido en otro redex. Otra definicin posible, subexpresin que se puede reemplazar por otra.

Forma normal: expresin que no contiene redexes (o sea, expresin que no se puede reducir). No todaexpresin tiene forma normal. La reduccin pretende obtener la formal normal.

Cul es el valor de infinito? Definido as:

infinito = infinito + 1

Visin denotacional: Botton (): valor terico que representa a un error o a una computacin que no termina.

Visin operacional: expresin cuyas computaciones no terminan (infinitos). expresin que no estn definidas (1/0).

Notas

No se puede manejar de manera operacional. No se puede preguntar si algo es sin obtener . Comparacin con da .

Funcin estricta: f = Si la funcin necesita el valor para dar el resultado entonces es estricta

Funcin no estricta: f 6=

Orden de evaluacin: algoritmo para la eleccin del redex a reducir.

Reduccin ms interna u orden aplicativo: primero los redexes ms internos. Tambin llamadaevaluacin impaciente.

Reduccin ms externa u orden normal: primero los redexes ms externos.

Nota: en ambos casos, si hay ms de un redex al mismo nivel, elige el de ms a la izquierda.

30 6.2. EVALUACIN PEREZOSA (O Lazy)

Propiedad 1. La reduccin ms externa tiene la propiedad importante de que si una expresin tieneforma normal, entonces sta la encontrar.

Cul es el resultado de evaluar en orden aplicativo la siguiente expresin:

fst (2, infinito) = fst (2, infinito + 1)= fst (2, infinito + 1 + 1)= fst (2, infinito + 1 + 1 + 1)= fst (2, infinito + 1 + 1 + 1 + 1).

.

.

Y cul es el resultado de evaluar la misma expresin en orden normal:

fst (2, infinito) = 2

Propiedad 2. Orden aplicativo TODAS las funciones son estrictasOrden normal hay funciones estrictas y no estrictas

Nota: la reduccin ms externa a veces puede necesitar ms pasos que la reduccin ms interna. Elproblema surge con cualquier funcin cuya definicin contenga apariciones repetidas de un argumento.Por ejemplo, el resultado de evaluar en orden aplicativo la siguiente expresin:

cuadrado (3 + 4)= < def. de + >

cuadrado 7= < def. de cuadrado >

7 * 7= < def. de * >

49

Y es el resultado de evaluar la misma expresin en orden normal:

cuadrado (3 + 4)= < def. de cuadrado >

(3 + 4) * (3 + 4)= < def. de + >

7 * (3 + 4)= < def. de + >

7 * 7= < def. de * >

49

Obsrvese que se necesit un paso ms porque en la definicin de cuadrado aparece repetido su argu-mento. Esto es:

cuadrado x = x * x

6. EVALUACIN 31

6.2. Evaluacin perezosa (o Lazy)Es una evaluacin en orden normal, con las siguientes caractersticas adicionales:

El argumento de una funcin slo se evala cuando es necesario para el cmputo. Un argumento no es necesariamente evaluado por completo; slo se evalan aquellas partes que

constituyen efectivamente al cmputo.

Si un argumento se evala, tal evaluacin se realiza slo una vez.

Ventajas

Termina siempre que cualquier otro orden de reduccin termine. No requiere ms (sino posiblemente menos) pasos que la evaluacin impaciente. Manipulacin de estructura de datos infinitas. Manipulacin de computaciones infinitas.

Desventajas

Es difcil calcular el costo de ejecucin.

Adoptaremos la evaluacin lazy como nuestro modelo de clculo porque tiene las propiedades desea-bles anteriormente mencionadas.Leer seccin 7.1 del libro.

ndice General1 Conceptos Importantes1.1 Valores1.2 Expresiones1.3 Funciones1.4 Ecuaciones orientadas1.5 Algunas definiciones1.6 Tipos

2 Sintaxis de Haskell2.1 Case sensitive2.2 Comentarios2.3 Definiciones de Variables2.4 Funciones2.4.1 Identificadores2.4.2 Operadores2.4.3 Relacin entre identificadores y operadores2.4.4 Definiciones de Funciones con Pattern Matching2.4.5 Definiciones con Guardas2.4.6 Definiciones recursivas2.4.7 Definiciones locales2.4.8 Expresiones case2.4.9 Aplicacin de Funciones

2.5 Secciones2.6 Tabla de precedencia/asociatividad de operadores2.7 Disposicin del cdigo

3 Cosas sobre el Hugs3.1 Prelude.hs3.2 Iniciando Hugs3.3 Comandos de Hugs3.4 Un programa en Haskell

4 Tipos de Haskell4.1 Booleanos4.2 Nmeros enteros4.3 Nmero en punto flotantes4.4 Caracteres4.5 Tipos de Funciones4.6 Listas4.7 Cadenas (String)4.8 Enumeraciones4.9 Tuplas4.10 Polimorfismo

5 Ms sobre funciones5.1 Funciones annimas (lambda abstracciones)5.2 Currificacin5.2.1 Forma prctica de ver la Currificacin

5.3 Composicin de Funciones5.4 Funciones totales y parciales.

6 Evaluacin6.1 Reduccin6.2 Evaluacin perezosa (o Lazy)

apunte haskell

Documents