PDF de programación - Introducción a la Programación Funcional en Haskell

Introducción a la Programación Funcional en Haskell

Gustavo Villavicencio1

1Facultad de Matemática Aplicada

Universidad Católica de Santiago del Estero

12 de Agosto, 2011

G. Villavicencio (FMA,UCSE)

Programación Funcional en Haskell

12 de Agosto, 2011

1 / 94

Ingeniería de documentos

Preliminares

Para entender el esquema de la presentación.

ghci

vim

file.lhs

lhs2TeX

file.tex

pdflatex

file.pdf

acrobat

G. Villavicencio (FMA,UCSE)

Programación Funcional en Haskell

12 de Agosto, 2011

2 / 94

Preliminares

Outline
1 Preliminares
2 Primera Parte

Paradigmas de programación
Importancia de la programación funcional
Resumen

3 Segunda Parte

El intérprete Hugs
Funciones
Expresiones usuales
Ejercicios
Operadores de orden superior
Ejercicios
Resumen

4 Tercera Parte: Clases de tipos

El sistema de tipos en Haskell
Tipos de datos
Polimorfismo
Ejercicios
Resumen

5 Mónadas

El problema
Operaciones de I/O
Ejercicios

G. Villavicencio (FMA,UCSE)

Programación Funcional en Haskell

12 de Agosto, 2011

3 / 94

Programación imperativa

Primera Parte

Paradigmas de programación

Programación imperativa
Los programas estás constituidos por sentencias (comandos) que alteran el
estado del mismo. Ejemplos: C++, Java, etc.

Características importantes:

En los programas imperativos el estado está compuesto por un
conjunto de variables.
El estado del programa cambia cuando alguna de las variables cambia.
σ = σ0 → σ1 → ··· → σn = σ.
Referential opaqueness - Efectos secundarios permitidos.
Programa imperativo: Conjunto de sentencias sobre cómo realizar los
cambios de estado.

G. Villavicencio (FMA,UCSE)

Programación Funcional en Haskell

12 de Agosto, 2011

4 / 94

Primera Parte

Paradigmas de programación

Programación funcional

Características I

El concepto de computación usado es el de función matemática. Esta
se define como un mapeo de valores de un tipo a valores de otro tipo.
La evaluación (ejecución) no es por transformación de la memoria sino
por aplicación de funciones a los argumentos de entrada: Lambda
calculus.

sumLista [ ]
sumLista (h : t) = h + sumLista t

= 0

sumLista[7, 5, 9] =sumLista(7 : [5, 9])
=7 + sumLista[5, 9]
=7 + sumLista(5 : [9])
=7 + 5 + sumLista[9]
=7 + 5 + sumLista(9 : [])
=7 + 5 + 9 + sumLista[]
=7 + 5 + 9 + 0
=21

G. Villavicencio (FMA,UCSE)

Programación Funcional en Haskell

12 de Agosto, 2011

5 / 94

Programación funcional

Primera Parte

Paradigmas de programación

Características II

El comportamiento funcional se refuerza: σ = f (σ) (asumiendo
programas determinísticos).
Transparencia referencial - Los efectos secundarios no están
permitidos. (Ejemplo en PresExamples.hs).
Lazy evaluation (Haskell en particular).
Ejemplos: Haskell, Scheme, etc.

Clasificación

Puros: Haskell, Miranda, Clean
Impuros: Standard ML, Scheme

G. Villavicencio (FMA,UCSE)

Programación Funcional en Haskell

12 de Agosto, 2011

6 / 94

Programación funcional

Primera Parte

Paradigmas de programación

Otras características:

Funciones como valores
Funciones de orden superior
Fuertemente tipado -> Inferencia de tipos
Parametrización
Pattern matching
Non-strict functions -> Lazy evaluation (Haskell)

G. Villavicencio (FMA,UCSE)

Programación Funcional en Haskell

12 de Agosto, 2011

7 / 94

Areas de aplicación de Haskell

Primera Parte

Paradigmas de programación

Finanzas
Comunicaciones (telefonía movil)
Biotecnología
IA
Seguros
Criptografía
Diseño de hardware
Tecnolología web

G. Villavicencio (FMA,UCSE)

Programación Funcional en Haskell

12 de Agosto, 2011

8 / 94

Por qué es importante la programación funcional?

Primera Parte

Importancia de la programación funcional

Abstracción y Claridad
Los programas funcionales en Haskell resaltan el algoritmo evitando
detalles de implementación. Como ya se dijo, enfatizan lo que tienen que
realizar en lugar de cómo tienen que hacerlo.

quicksort [ ]
quicksort (x : xs) = quicksort [e | e ← xs, e < x ] ++

= [ ]

[x ] ++
quicksort [e | e ← xs, e x ]

G. Villavicencio (FMA,UCSE)

Programación Funcional en Haskell

12 de Agosto, 2011

9 / 94

Por qué es importante la programación funcional?

Primera Parte

Importancia de la programación funcional

Abstracción y Claridad
Los programas funcionales en Haskell resaltan el algoritmo evitando
detalles de implementación. Como ya se dijo, enfatizan lo que tienen que
realizar en lugar de cómo tienen que hacerlo.

quicksort [ ]
quicksort (x : xs) = quicksort [e | e ← xs, e < x ] ++

= [ ]

[x ] ++
quicksort [e | e ← xs, e x ]

G. Villavicencio (FMA,UCSE)

Programación Funcional en Haskell

12 de Agosto, 2011

9 / 94

Primera Parte

Importancia de la programación funcional

Abstracción y Claridad (Continuación)
Poseen mecanismos sofisticados de abstracción: Operadores de orden
superior.

sumListaf = foldr (+) 0
prodListaf = foldr (∗) 1

G. Villavicencio (FMA,UCSE)

Programación Funcional en Haskell

12 de Agosto, 2011

10 / 94

Por qué es importante la programación funcional?

Primera Parte

Importancia de la programación funcional

Precisión
Los programas funcionales son apropiados para el razonamiento ecuacional
gracias a la transparencia referencial.

Visión imperativa : Programas = Estructuras de datos + algoritmos
Visión funcional : Algebra = Objetos + operadores

Para observar esto, nos sumergimos en las “aguas profundas” de la
programación funcional.

G. Villavicencio (FMA,UCSE)

Programación Funcional en Haskell

12 de Agosto, 2011

11 / 94

Por qué es importante la programación funcional?

Primera Parte

Importancia de la programación funcional

Precisión
Los programas funcionales son apropiados para el razonamiento ecuacional
gracias a la transparencia referencial.

Visión imperativa : Programas = Estructuras de datos + algoritmos
Visión funcional : Algebra = Objetos + operadores

Para observar esto, nos sumergimos en las “aguas profundas” de la
programación funcional.

G. Villavicencio (FMA,UCSE)

Programación Funcional en Haskell

12 de Agosto, 2011

11 / 94

Por qué es importante la programación funcional?

Primera Parte

Importancia de la programación funcional

Ejemplo de razonamiento ecuacional
Consideremos el tipo de datos listas en Haskell

data Lista a = Nil | Cons a (Lista a)

desde donde derivamos el functor: FA : () + A × I

Sobre tipos de datos

Sobre funciones

type FA B = () + A × B

FA
FA f = id + id × f

::

(A −→ B) −→ (FA A −→ FA B)

G. Villavicencio (FMA,UCSE)

Programación Funcional en Haskell

12 de Agosto, 2011

12 / 94

Por qué es importante la programación funcional?

Primera Parte

Importancia de la programación funcional

Ejemplo de razonamiento ecuacional (continuación I)
Supongamos además dos FA-algebras (A, [Nil , Cons]) and (Z, [0, +]) de la
categoria Alg(F) de F-Algebras

Nil es el operador de secuencia vacía: Nil : 1 −→ L.
Cons es el constructor de secuencias: Cons : A × L −→ L.
(A, [Nil , Cons]) es un algebra inicial y (Z, [0, +]) es un algebra
arbitraria.

G. Villavicencio (FMA,UCSE)

Programación Funcional en Haskell

12 de Agosto, 2011

13 / 94

Por qué es importante la programación funcional?

Primera Parte

Importancia de la programación funcional

Ejemplo de razonamiento ecuacional (continuación II)
Homomorfismo: Traslación estructural entre objetos de una categoría.

A

h

Z

[Nil,Cons]

[0,+]

1 + Int × A
id+id×h

1 + Z × Z

(1)

G. Villavicencio (FMA,UCSE)

Programación Funcional en Haskell

12 de Agosto, 2011

14 / 94



o
o


o
o
Por qué es importante la programación funcional?

Primera Parte

Importancia de la programación funcional

Ejemplo de razonamiento ecuacional (continuación III)
Proceso de cálculo en notación pointfree. Notación pointfree?

dupAddPW x y = 2 ∗ x + y
dupAddPF = (+) ◦ (2∗)

-- Pointwise example
-- Pointfree example

h · [Nil, Cons]

[0, +] · (id + id × h)

[0 · id, + · (id × h)]

[0, + · (id × h)]

= from commutative diagram

= + − absorption

= identity

(2)

G. Villavicencio (FMA,UCSE)

Programación Funcional en Haskell

12 de Agosto, 2011

15 / 94

Por qué es importante la programación funcional?

Primera Parte

Importancia de la programación funcional

Ejemplo de razonamiento ecuacional (continuación IV)
Siguiendo con el proceso de cálculo reordenamos la ecuación

h · [Nil , Cons] = [0, + · (id × h)]

por la propiedad de fusión de la suma

[h · Nil , h · Cons] = [0, + · (id × h)]

por igualdad estructural del operador

h · Nil

= 0

h · Cons = + · (id × h)

G. Villavicencio (FMA,UCSE)

Programación Funcional en Haskell

12 de Agosto, 2011

16 / 94

Porqué es importante la programación funcional

Primera Parte

Importancia de la programación funcional

Ejemplo de razonamiento ecuacional (continuación V)
En notación pointwise las ecuaciones previas se reescriben como

(h · Nil )x

(h · Cons)(a, xs) = ( + · (id × h))(a, xs)

=

0x

Aplicando definición de composición, de función constante, de producto de

funciones y de suma h Nil

= 0

h Cons(a, xs) = a + h xs

Las ecuaciones finales corresponden a una función ejecutable en
HASKELL!!!

G. Villavicencio (FMA,UCSE)

Programación Funcional en Haskell

12 de Agosto, 2011

17 / 94

Por qué es importante la programación funcional?

Primera Parte

Importancia de la programación funcional

Capacidad de reuso
Gracias a los mecanismos algebraicos subyacentes en un lenguanje
puramente funcional como Haskell, las posibilidades de reuso son
significativas.

Recordemos (1). Qué ocurre si cambiamos la FA-algebra (Z, [0, +]) por otra
idéntica desde una perspectiva abstracta, es decir, isomórfica: (N, [1,∗])

G. Villavicencio (FMA,UCSE)

Programación Funcional en Haskell

12 de Agosto, 2011

18 / 94

Por qué es importante la programación funcional?

Primera Parte

Importancia de la programación funcional

Capacidad de reuso (continuación I)
Simplemente

h Nil

h Cons(a, xs) = a ∗ h xs

= 1

(3)

reusando todo el proceso de cálculo!
Más aún podemos reusar el esquema de recursión completo: Funciones de
orden superior

h = foldr (∗