calculo de programas

ESTOS APUNTES AUNQUE ESTAN REDACTADOS PARA HASKELL

SON VALIDOS PARA LA PARTE FUNCIONAL DEL LENGUAJE CURRY

Funciones de Plegado sobre listas
´
JOSE E. GALLARDO RUIZ

Lecci´n Magistral
o

´
Indice General
Introducci´n
o
1 Breve introducci´n a Haskell
o
1.1 Tipos
1.2 Funciones de orden superior o combinadores
1.3 Aplicaci´n parcial
o
1.4 Listas
1.5 Polimorfismo
1.6Razonamiento ecuacional. Inducci´n
o
2 Funciones de plegado
2.1 foldr
2.2 foldl
3 La propiedad universal de foldr
3.1 La propiedad universal como principio de prueba
3.2 S´
ıntesis de programas v´ la propiedad universal
ıa
4 Fusi´n de plegados
o
4.1 Un teorema de fusi´n para foldr
o
4.2 Un teorema de fusi´n para foldl
o
5 Relaci´n entre foldr y foldl
o
5.1 Primer Teorema de dualidad
5.2Segundo Teorema de dualidad
5.3 Tercer Teorema de dualidad
Referencias

1
1
1
2
3
4
5
6
8
8
12
14
15
16
18
18
22
26
26
27
28
29

1

Funciones de Plegado sobre listas
Introducci´n
o

Muchos algoritmos sobre listas son expresados de un modo natural recursivamente
y sus propiedades suelen ser demostradas mediante la t´cnica de inducci´n estruce
o
tural. De hecho,estos algoritmos siguen un mismo patr´n recursivo y las pruebas
o
comparten un patr´n inductivo com´n. Tener que repetir estos patrones varias veces
o
u
es tedioso, consume demasiado tiempo y puede dar lugar a errores. Estos inconvenientes pueden ser evitados utilizando una funci´n de orden superior y un principio
o
de prueba que los capture, lo cual nos permitir´ concentrarnosexclusivamente en
a
las partes espec´
ıficas de cada algoritmo. El principio de prueba servir´ no solo como
a
un m´todo que simplifica la inducci´n, sino como un principio de definici´n que
e
o
o
puede ser utilizado para derivar programas de un modo sistem´tico.
a
El objetivo de esta lecci´n es presentar estas t´cnicas de generalizaci´n en el
o
e
o
marco de un lenguaje funcional moderno comoHaskell. Las t´cnicas pueden ser
e
aplicadas a cualquier lenguaje funcional puro (que permita el razonamiento ecuacional) y pueden ser extendidas a otras estructuras de datos como los ´rboles,
a
aunque no desarrollaremos esta posibilidad.
La organizaci´n de la lecci´n es la siguiente: En la primera secci´n realizaremos
o
o
o
una breve introducci´n al lenguaje de programaci´n (Haskell), enespecial las cao
o
racter´
ısticas de ´ste que ser´n necesarias en el resto de la lecci´n. En la segunda
e
a
o
secci´n presentaremos las funciones de plegado sobre listas f oldr y foldl . La tercera
o
secci´n est´ dedicada a la propiedad universal de la funci´n foldr y sus aplicaciones.
o
a
o
La cuarta secci´n estudia los teoremas de fusi´n correspondientes a cada una de las
o
ofunciones de plegado. Por ultimo, la secci´n quinta trata los teoremas de dualidad
´
o
que establecen las relaciones entre las dos funciones de plegado.
1 Breve introducci´n a Haskell
o
Haskell (Peyton Jones 99; Thompson 99) es un lenguaje funcional fuertemente tipificado, puro y no estricto. La pureza del lenguaje indica que est´ libre de efectos
a
laterales, lo cual permite razonar sobre losprogramas del mismo modo que se puede
hacer en matem´ticas, reemplazando expresiones por otras equivalentes. El car´cter
a
a
no estricto del lenguaje indica que los argumentos de las funciones no son evaluados
antes de reemplazarlos en el cuerpo de ´sta, es decir se usa un orden no aplicativo
e
para implementar el lenguaje. Esta caracter´
ıstica permite, entre otras cosas, trabajar conestructuras de datos infinitas en los programas. La tipificaci´n est´tica del
o
a
lenguaje hace que cada elemento de un programa tenga asignado un tipo. Los tipos
se usan en tiempo de compilaci´n para detectar errores en el programa.
o
1.1 Tipos
El tipo de una funci´n se escribe separando mediante el constructor → los tipos
o
de los distintos argumentos y el resultado. Por ejemplo, la funci´n...