PDF de programación - Clase 19 - Programación Funcional Haskell

Programación Funcional

Haskell
Clase 19

José Raymundo Marcial Romero

[email protected]

BUAP

cJosé Raymundo Marcial Romero. Clase Número 19 – p.1/23

Temas de la clase

• Lenguajes Funcionales
• Haskell y Hugs
• Sesiones y scripts
• Valores y Representaciones
• Evaluaciones
• Funciones y Operadores
• Definiciones
• Tipos
• Una sesion de Hugs

• Comenzar y terminar una sesión
• Creación y edición de scripts
• Carga y ejecución de scripts
• Otros comandos útiles

cJosé Raymundo Marcial Romero. Clase Número 19 – p.2/23

Lenguajes Imperativos y Funcionales

• Lenguaje humano = lenguaje Natural

• Sentencias en lenguaje natural

• Imperativas
• Declarativas
• Interrogativas
• Exclamativas

• En lenguajes de programación:

• Sentencias Imperativas

x := 5

• Sentencias declarativas

function f(int x) { return x+1;}

cJosé Raymundo Marcial Romero. Clase Número 19 – p.3/23

Lenguajes Imperativos y Funciones

La distinción entre construcciones imperativas y declarativas
se basa en la distinción entre cambiar un valor existente y
declarar un nuevo valor.

{ int x=1;

/* declara una nueva variable x */

x = x+1;

/* asigna un valor a x */

{ int y=x+1;

/* declara una nueva variable y */

{ int x=y+1;

/* declara una nueva x */

}}}

Lenguaje funcional: se utiliza para referirse a un lenguaje de
programación en el cual la mayoría de cálculos se realiza mediante la
evaluación de expresiones que contienen funciones.

Ejemplos: Lisp, ML y Haskell.

cJosé Raymundo Marcial Romero. Clase Número 19 – p.4/23

Lenguajes Funcionales-1

• Los lenguajes funcionales ofrecen al programador un

buen número de recursos que permiten resolver
problemas complejos mediante programas pequeños y
robustos.

• Sistema de tipos polimórficos.
• Definir funciones que aceptan otras funciones.
• Definir y manipular estructuras de datos infinitas.
• Modelo computacional simple, claro y bien

fundamentado.

cJosé Raymundo Marcial Romero. Clase Número 19 – p.5/23

Lenguajes Funcionales-2

Quick sort en un lenguaje funcional
qsort []

= []

qsort (x:xs) = qsort elts_lt_x ++ [x] ++ qsort elts_greq_x

where

elts_lt_x

= [y | y <- xs, y < x]

elts_greq_x = [y | y <- xs, y >= x]

cJosé Raymundo Marcial Romero. Clase Número 19 – p.6/23

Lenguajes Funcionales-3

qsort( a, lo, hi ) int a[], hi, lo;

{

int h, l, p, t;

if (lo < hi) {

l = lo;

h = hi;

p = a[hi];

do {

while ((l < h) && (a[l] <= p))

l = l+1;

while ((h > l) && (a[h] >= p))

h = h-1;

if (l < h) {

t = a[l];

a[l] = a[h];

a[h] = t;

}

} while (l < h);

t = a[l];

a[l] = a[hi];

a[hi] = t; qsort( a, lo, l-1 );

qsort( a, l+1, hi );

cJosé Raymundo Marcial Romero. Clase Número 19 – p.7/23

} }

Quién utiliza lenguajes funcionales

• Software AG, una de las mayores empresas de software en

Alemania vende un sistema experto.

• Ericsson ha desarrollado un nuevo lenguaje de programación

funcional, Erlang, que se utilizará en sus aplicaciones de
teléfono.

• Query es el lenguaje de consulta del sistema de base de datos

orientado a objetos O2

• ICAD Inc market un sistema CAD para ingeniería mecánica y

aeronáutica.

cJosé Raymundo Marcial Romero. Clase Número 19 – p.8/23

Haskell y Hugs

• Haskell es un lenguaje de programación funcional ”lazy”

• Programar en un lenguaje de programación funcional consiste

en construir definiciones de funciones (matemáticas) y
estructuras de datos, y expresiones que usan estas definiciones.
La ejecución de un programa funcional consiste en la
evaluación de las expresiones que forman el programa.

• HUGS significa Haskell Users’ Gofer System. Provee un

intérprete el cual acepta el lenguaje Haskell. El uso de Hugs
consiste de:

• inicio de sesiones
• creación de scripts

cJosé Raymundo Marcial Romero. Clase Número 19 – p.9/23

Sesiones

El rol primario de la computadora es actuar como un evaluador:

• Escribimos una expresión seguida de una nueva línea.

• La computadora evalúa la expresión, y muestra el resultado.

Prelude> 63 la expresión 63 está en su forma más simple

63

Prelude> 7*9 7*9 se simplifica realizando la multiplicación

63

Prelude> False && True

False

cJosé Raymundo Marcial Romero. Clase Número 19 – p.10/23

Script - 1

Un script se guarda como un archivo script.hs

// Ejemplo de un script

square :: Integer -> Integer

square x = x*x

greater:: (Integer, Integer) -> Integer

greater (x,y) = if x>=y then x else y

Una sesión que utiliza script.hs

Prelude> :load script.hs

script> square 12

144

script> greater (square 3, 4+3)

9

cJosé Raymundo Marcial Romero. Clase Número 19 – p.11/23

Valores y Representaciones

• En programación funcional una expresión denota un valor. Los

valores pueden ser: números de varias clases, valores de
verdad, funciones, caracteres, tuplas, listas.

• Los valores se reconocen y manipulan vía representaciones

concretas. El mismo valor puede tener más de una
representación. Cuarenta se puede representar como 40 ó 8*5.

• Hugs imprime un valor, en su representación canónica. La

forma canónica de cuarenta es 40. La forma canónica de
cualquier expresión depende de:

• la sintaxis para construir la expresión;
• Las reglas de evaluación (ó reducción).

cJosé Raymundo Marcial Romero. Clase Número 19 – p.12/23

Evaluación - 1

• Evaluar una expresión significa reducirla a su forma

equivalente más simple, que es su representación canónica.
Los términos evaluación, simplificación y reducción son
equivalentes.

• Pueden existir diferentes secuencias de reducción para evaluar

la misma expresión:

square (3+2)

square (3+2)

= por la definición de +

= por la definición de square

square 5

(3+2) * (3+2)

= por la definición de square

= por la definición de +

5*5

5 * (3+2)

= por la definición de *

por la definición de +

25

5*5

= por la definiciónde *

25

cJosé Raymundo Marcial Romero. Clase Número 19 – p.13/23

Evaluación Lazy
• Algunas veces las reducciones no terminan:

three :: Integer -> Integer

infinity :: Integer

three x = 3

infinity x = infinity + 1

three infinity

three infinity

= por definición de infinity = por definición de three

three (infinity + 1)

3

= por definición de infinity

three ((infinity +1)+1)

...

• Haskell es un lenguaje Lazy: implementa una estrategia de

reducción llamada evaluación lazy que garantiza terminación
siempre y cuando sea posible.

cJosé Raymundo Marcial Romero. Clase Número 19 – p.14/23

Funciones y Operadores

• Función: regla de correspondencia que asocia cada elemento

de un tipo A con un único elemento de tipo B

• delta :: (Float, Float, Float) -> Integer
• plusc :: Integer -> (Integer -> Integer)

• La aplicación de funciones tiene precedencia

• square square 3 significa (square square) 3, así que

debemos escribir square (square 3)

• square 3+4 significa (square 3) +4 así que debemos

escribir square (3+4).

• Operador: una función binaria que se puede escribir entre sus

dos argumentos (notación infija):

• 5 <= 9
• 15 ‘div‘ 4

cJosé Raymundo Marcial Romero. Clase Número 19 – p.15/23

Definiciones- 1

Declaraciones

pi:: Float

3.14159

Expresiones condicionales

greater:: (Integer,Integer)->Integer

Ecuaciones guarded

greater:: (Integer,Integer)->Integer

greater(x,y)=if x>=y then x else y

greater(x,y)

| x>=y = x

| x<y = y

• sintaxis de expresiones guarded:

• Una secuencia de cláusulas, delimitadas por una barra

vertical

• por cada cláusula una condición
• y una expresión asociada a ésta.

cJosé Raymundo Marcial Romero. Clase Número 19 – p.16/23

Definiciones-2

Considere lo siguiente:

signum:: Integer -> Integer

signum x = if x<0 then -1 else

if x==0 then 0 else 1

Si se utilizan ecuaciones guarded la definición es más clara:

signum:: Integer -> Integer

signum x

| x<0 = -1

| x==0 = 0

| x>0 = 1

cJosé Raymundo Marcial Romero. Clase Número 19 – p.17/23

Tipos

• El universo de valores esta particionado en colecciones

organizadas llamadas tipos.

• Existen operaciones asociadas con cada tipo.

• Cada expresión bien formada tiene asignado un tipo (strong

typing)

• Permite detectar ciertos errores antes de la evaluación
• Le crea al programador una buena disciplina de escritura

de programas

cJosé Raymundo Marcial Romero. Clase Número 19 – p.18/23

Tipos básicos y operadores

Tipos

Bool

Eq

Ord

Int

Integer

Integral

Valores

True y False

Operadores

|| (or) && not (no)

clases con igualdad

==(Igual) /= (Diferente)

Clases de orden

< > <= >= min max

Entero de precisión simple

+ - * ?

Entero de precisión arbitraria

Integer Int

gcd lcm div mod

Float

Punto flotante de precisión simple

Double

Punto flotante de precisión doble

Fraction

Float Double

/

x div y = ⌊x/y⌋ donde ⌊x⌋ es el entero n más grande tal que n ≤ x

x = (x div y) ∗ y + (x mod y)

cJosé Raymundo Marcial Romero. Clase Número 19 – p.19/23

Inicio y Termino de sesiones

Bajo Unix

• Inicio: teclear hugs

• salir: teclar :quit o :q

Bajo Windows NT

• Elegir Inicio, Programas, Hugs98

• Elegir Hugs (Haskell98 mode) para tener la misma interfaz

que en Unix

• Elegir WinHugs para tener una interfaz gráfica

cJosé Raymundo Marcial Romero. Clase Número 19 – p.20/23

Creación y Edición de scripts
• Los scripts son colecciones de definiciones que se pueden

almacenar en un archivo.

• Los archivos que terminan con la extensión hs siempre se

consideran como scripts de Hugs

• Si desea escribir comentario hay dos formas {− y −} o −− .

Ejemplos.

{- Esto es un comentario -}

-- También esto es un comentario

• Para crear y editar un script, se pueden utilizar los siguientes

editores:

• vi, emacs, xemacs, pico, bajo Unix
• Notepad o Wordpad, bajo Windows

cJosé Raymundo Marcial Romero. Clase Número 19 – p.21/23

Cargar y Ejecutar un script

• Los scripts en Hug