Algoritmos y Estructuras de Datos I

Facultad de Ciencias Exactas y Naturales

Universidad de Buenos Aires

Primer Cuatrimestre de 2000

Práctica 2

Fecha sugerida de finalización: 27/4/2000.

Programación Funcional

Notación

Para escribir las funciones, usaremos la sintaxis de Gofer, tal como se ve en el taller. De esta manera, se pueden probar en la máquina las funciones definidas. Sin embargo, los tipos básicos usados en estas prácticas no coinciden exactamente con los tipos básicos de Gofer. Por ejemplo, el tipo Nat no existe en Gofer y aquí lo usaremos como básico.

Las aridades de las funciones se dan currificadas, esto es, todas las funciones reciben un solo argumento, y pueden devolver, eventualmente, una función. La currificación reemplaza los argumentos estructurados de una función por una secuencia de argumentos simples, para permitir un tratamiento homogéneo.

Veamos un ejemplo:

La función suma (+) recibe dos naturales y devuelve otro natural (que es la suma de los dos argumentos). Uno escribiría la aridad de la función + de la siguiente manera:

+ :: Nat � Nat � Nat

Currificando, lo que hacemos es convertir el par de argumentos de la siguiente manera:

+ :: Nat � Nat � Nat

Aclaraciones

Esta práctica pide la definición de funciones, al estilo de los programas funcionales de Gofer. En general, no hay una única manera de definir una función. Sin embargo, nos interesa que las soluciones elegidas sean claras, comprensibles, compactas (breves, de ser posible), completas (que contemplen todos los casos de interés) y declarativas (que estén más cerca del qué y no del cómo).

Cuando resulte conveniente, se pueden definir funciones auxiliares para hacer más fácil la definición de la función principal. También se pueden usar funciones definidas previamente en otros ejercicios.

Dar explícitamente la aridad de una función (el tipo de su domino y su imagen) permite detectar errores tempranamente. No hay que olvidar que el valor que devuelve una función depende sólo de sus argumentos.

Ejercicio 1

i.       Definir la función parcial f : N � N, definida por extensión de la siguiente manera:

f (1) = 8

f (4) = 131

f (16) = 16

ii.     Análogamente, definir la función parcial g : N � N :

g (8) = 16

g (16) = 4

g (131) = 1

iii.    A partir de las funciones definidas en i y ii, definir las siguientes funciones parciales:

h = f o g

k = g o f

Ejercicio 2

Se tiene definido el tipo Nat con los siguientes elementos contructores:

•       0 (cero)

•       Suc(Nat) (el sucesor del número pasado como parámetro)

Empleando solamente 0 y suc, definir las siguientes funciones:

i.                     igual :: Nat � Nat � Bool

ii.                    suma :: Nat � Nat � Nat

iii.                  producto :: Nat � Nat � Nat

iv.                  potencia :: Nat � Nat � Nat

v.                   menor :: Nat � Nat � Bool

vi.                  resta :: Nat � Nat � Nat (es 0 si el minuendo es menor que el sustraendo)

vii.                división :: Nat � Nat � Nat (división entera; por ejemplo, división 7 3 = 2)

viii.               resto :: Nat � Nat � Nat

ix.                   mcd :: Nat � Nat � Nat (máximo común divisor)

x.                    factorial :: Nat � Nat

xi.                   número_combinatorio :: Nat � Nat � Nat

xii.                 n_Fibonacci :: Nat � Nat (n-ésimo término de la sucesión de Fibonacci)

Ejercicio 3

Definir las siguientes funciones, utilizando las definidas en el ejercicio 2.

i.                     par :: Nat � Bool

ii.                    impar :: Nat � Bool

iii.                  par :: Nat � Bool (redefinirla usando solamente resta y recursión)

iv.                  divisor :: Nat � Nat � Bool (el primer parámetro divide al segundo)

v.                   cuadrado_perfecto :: Nat � Bool

vi.                  suma_divisores :: Nat � Nat (devuelve la suma de los divisores)

vii.                perfecto :: Nat � Bool (n es perfecto si la suma de los divisores propios de n es igual a n)

viii.               mayor_divisor :: Nat � Nat (devuelve el mayor divisor propio)

ix.                   primo :: Nat � Bool

x.                    siguiente_primo :: Nat � Nat (devuelve el primer primo mayor)

Ejercicio 4

Definir las siguientes funciones, de naturales en naturales:

i.                    

ii.                  

iii.                 

Ejercicio 5

i.                     Sea f(0) = 0, f(1) = 1, f(2) = 2², f(3) = 3³³ = 3²⁷, etc.. Definir la función f (dar la aridad también).

ii.                    Sea A :: Nat � Nat � Nat (notar que esta función no está currificada)
A(Suc(i), Suc(x)) = A(i, A(Suc(i), x))
A(i, 0) = 1
A(0, x) = x + 1 si x = 0, 1
A(0, x) = x + 2 si x > 1
Calcular A(1, 1), A(2, 2) y A(3, 2).

iii.                  Sea A :: Nat � Nat � Nat
A(Suc(i), Suc(x)) = A(i, A(Suc(i), x))
A(i, 0) = 1
A(0, x) = x + 1 si x = 0, 1
A(0, x) = x + 2 si x = 2
¿Qué ocurre si se quiere evaluar la expresión A( A(2, 0) - 1 , A(2, 2) - 1 ) ?

Ejercicio 6

Definir los conectivos lógicos � y � (NAND y NOR, respectivamente), vistos en la práctica 1. Basarse en las tablas de verdad de los símbolos, sin usar otras operaciones lógicas.

�Ejercicio 7

Definir la función divisible_por_tres :: Nat � Bool, que dice si un número es divisible por tres o no, usando el criterio de divisibilidad por tres (Un número es divisible por tres si y solo si la suma de sus cifras también lo es).