Programación funcional

En las primeras clases de la materia de Programación I, en la que vemos el paradigma de programación funcional, hemos explorado diferentes tipos de datos  y operaciones con ellos. Mediante ese análisis hemos llegado a explorar conceptos importantes como la composición de funciones y elementos estructurales del lenguaje Scheme como la declaración de funciones, reglas de contexto léxico (local) y finalmente declaración y uso de estructuras.

Las estructuras resuelven la necesidad de crear nuevos tipos de datos que en sí mismos están compuestos por varios componentes de cualquier otro tipo. Sin embargo, todavía no sabemos cómo manejar un conjunto de datos con el mismo patrón, por ejemplo, cómo se resolvería un llamado de la siguiente forma:

(transferir estudiantes profesor)

en la que estudiantes es un conjunto de datos de tipo estudiante, estructura definida de la siguiente manera:

(define-struct estudiante (nombre apellido profesor nota))

El llamado en cuestión, debería efectuar su acción sobre cada uno de los datos del conjunto, por ejemplo cambiarles a todos el profesor por lo que contenga el parámetro del mismo nombre.

Otra cosa que todavía no sabemos hacer es devolver en un sólo llamado más de un valor. Scheme tiene como característica fundamental que todas las expresiones se convierten en un sólo valor. ¿Qué pasa si yo quisiera que una función devolviera dos objetos de naturalezas totalmente diferentes, por ejemplo, que la operación de transferencia del ejemplo devolviera el conjunto de estudiantes modificados y simultáneamente true o false si la operación tuvo éxito o no?. Aunque alguien podría responder que creando una nueva estructura con los componentes que queremos retornar, esa solución viola un poco el propósito de una estructura, que es un dato cuyos elementos están estrechamente relacionados.

La solución a éste tipo de problemas es un tipo de datos muy general llamado listas. Para resolver los problemas anteriores la solución sería que la función transferir de los párrafos anteriores recibiera una lista de estudiantes y devolviera una lista compuesta por el grupo de estudiantes modificados y un valor booleano. A continuación se elaborará el concepto de listas y su uso, explorando de paso el concepto de recursividad. Disfrútenlo.

Listas y conjuntos de datos

Como veníamos viendo en los párrafos anteriores, sólo hemos considerado operaciones sobre operandos atómicos, como en el ejemplo anterior (transferir estudiante profesor),  en el que se hace un llamado a una función cuyos parámetros son una estructura estudiante y un símbolo profesor, el resultado es una nueva estructura estudiante cuyo profesor es reemplazado por el contenido del argumento profesor. Ésto no es realista porque, aunque la función es útil ya que resuelve parte del posible problema, la única manera de cambiar un conjunto de estudiantes sería escribir tantas líneas como estudiantes haya y ese no es un número que sea siempre igual, es decir, si se escribe un programa que transfiera 5 estudiantes a cierto profesor, sólo funcionaría para ese número. ¿Qué hacer si fueran más de 5 o menos que eso?. Nuestro programa no sería flexible.

Las listas son la manera de agrupar elementos de tipo arbitrario en cantidad arbitraria, es la estructura de datos más general posible. Por ejemplo:

(list 1 ‘a “c”)

es una lista de tres elementos, el primero es un dato de tipo número, el segundo es un dato de tipo símbolo y el tercero es de tipo cadena de texto. Así como se usan los tipos primitivos (números, cadenas, caracteres, booleanos y funciones) también se pueden usar un nuevo tipo definido por el usuario, por ejemplo la estructura estudiante que hemos estado citando:

(define-struct estudiante (nombre apellido profesor nota))
;; estudiante es una estructura, en la que si x es un dato de tipo estudiante, (estudiante-nombre x), (estudiante-apellido x), (estudiante-profesor x) son valores de tipo símbolo y (estudiante-nota x) es de tipo número.

(list (make-estudiante ‘Pedro ‘Vargas ‘Vargas 5) (make-estudiante ‘juan ‘salas ‘vargas 5) (make-estudiante ‘Sandra ‘Moreno ‘Vargas 5) )

el significado de la última línea podría ser haga una lista de 3 estudiantes que estudian con el profesor Vargas: Pedro Vargas cuya nota es 5, Juan Salas cuya nota es 5 y Sandra Moreno cuya nota es 5.

Una lista se puede considerar una estructura definida en términos de sí misma:

Una lista es un grupo de elementos compuesta por el primer elemento y una lista los elementos restantes.

Lo anterior escrito en Scheme sería:

(define l (cons ‘a ‘(b c d)))

Una lista de símbolos se puede crear de varias formas, una es como lo hemos venido haciendo (list ‘a ‘b ‘c) pero también se puede hacer mediante la expresión ‘(a b c), donde ‘a ‘b y ‘c son los elementos de la lista.

Por otro lado, la expresión (cons a l), también crea una lista, pero su interpretación es como la definición anterior: a es un elemento y l es una lista con el resto de los elementos. A una definición de esta naturaleza (definida en términos de ella misma) se le conoce como definición recursiva de una lista y algunos textos definen las listas como una estructura autorreferenciada o recursiva. Ahora nos enfrentamos a un problema: ¿cómo definir una lista con un sólo elemento?, es decir, ¿qué sería la “lista con el resto de los elementos” para una lista de un sólo elemento?.

Una lista de un sólo elemento se puede construir ordinariamente con la función list, por ejemplo (list ‘a) crea una lista de un sólo elemento, el símbolo ‘a. Por otro lado, para poder usar la definición recursiva, podemos considerar que una lista de un sólo elemento está compuesta por un elemento seguido de la lista vacía y ésto (equivalente a una lista de un sólo elemento) se escribiría (cons ‘a empty).

Para retomar el primer ejemplo, reescrito de manera recursiva se sería:

(define l (cons ‘a (cons ‘b (cons ‘c empty) ) ) )

La línea anterior define una lista construyendola mediante un elemento seguido de la construcción del resto de la lista. Para repasar qué pasa miremos cómo Scheme convierte la expresión anterior en un dato puntual:

(define l (cons ‘a (cons ‘b (list ‘c) ) ) ) → (define l (cons ‘a (list ‘b ‘c) ) ) → (define l (list ‘a ‘b ‘c ) )

Una definición recursiva consiste en un caso base (un elemento) y un caso simplificado del problema (el resto de la lista -n elementos menos el primero). Aunque la nueva definición escrita es mucho más compleja que la primera, estructuralmente es más simple, dado que no enumera todos los elementos sino la forma general de la lista. En otras palabras, define la lista a partir de una operación, una regla de construcción.

Ejercicio:

1. Crear listas de números consecutivos de 1 a 5 usando la definición recursiva
2. Crear una estructura estudiante que tenga los elementos nombre, apellido, curso y nota, donde los primeros 3 son símbolos y el último un número, a continuación cree una lista de 5 estudiantes usando la definición recursiva.
3. Cree una lista de listas, compuesta por una lista de números de 1 a 5 y una lista de 5 estudiantes. La lista anterior podría servir para asignar a un grupo de estudiantes, sus respectivas notas.
4. Ejecute la siguiente instrucción (rest (list ‘a)) e interprete el resultado. ¿Qué es empty?

Operaciones con listas

A estas alturas hemos estado usando un las listas sin definir qué operadores permite, a excepción de las funciones list y cons, cuyas diferencias hay que pensar muy bien, dado que list recibe un conjunto de elementos que componen el resultado de la operación, mientras que cons recibe un par elemento-lista y los junta como resultado en una nueva lista.

Los operadores primitivos de las listas son los siguientes:

1. (list <elementos>) : crea una lista nueva a partir de la enumeración de sus elementos -se escriben todos los elementos-
2. (cons <elemento> <lista>): construye una nueva lista compuesta por el primer elemento seguido de los elementos de <lista>
3. (empty? <lista>): Devuelve true si la lista está vacía (no tiene elementos) y false si la lista contiene por lo menos un elemento
4. (list? x): Devuelve true si x es una lista o false en caso contrario.
5. (first <lista>): Devuelve el primer elemento de la lista
6. (rest <lista>): Devuelve una lista sin el primer elemento (resto de la lista).
7. (length <lista>) : devuelve el número de elementos de la lista

Ejercicio: Use los operadores anteriores sobre las listas del primer ejercicio para comprobar el resultado. Haga variantes de los ejercicios, úselos en ellos los operadores.

Los ejercicios anteriores reflejan la generalidad de las listas: pueden contener cualquier tipo de elementos: desde los más simples (números) hasta los que pueden ser más complejos (estructuras), incluso otras listas.

Cuando una lista tiene elementos de un solo tipo la llamaremos una lista homogénea y es similar al concepto de vectores o arreglos en otros lenguajes, por otro lado una lista no homogénea es más difícil de tratar. Una lista homogenea obedece naturalmente a una definición recursiva: primer elemento seguido de una lista de elementos y el caso base es el de un sólo elemento definido como el elemento seguido por la lista vacía.
Ya sabiendo cómo crear listas, ahora tenemos que estudiar cómo sacar elementos de ellas. Con base en la definición recursiva de una lista, los únicos operandos válidos para obtener algún elemento serían first y rest. Ejemplo:

(frst (list ‘(a b c)) → ‘a

(rest (list ‘(a b c)) → ‘c

Ésto nos enfrenta con un nuevo reto: ¿cómo sacar un elemento diferente del primero usando la definición recursiva?. Para una lista de tamaño fijo es fácil:

Ejemplo: Sacar el tercer elemento de la lista l:

(define l ‘(a b c))

(first (rest (rest l))) → (first (rest (list ‘b ‘c))) → (first (list ‘c)) → ‘c

Si la lista anterior fuera de más elementos, sólo habría que concatenar más operaciones rest hasta que se recorriera toda la lista hasta el último elemento, momento en el cual se usaría first y se obtendría el primer elemento de una lista a la que se le han eliminado sistemáticamente los primeros elementos hasta llevarla a una lista compuesta sólo por el último elemento de la lista original.

Esto sugiere que las operaciones sobre listas de tamaño arbitrario requieren de funciones que se llamen a sí mismas.

Ejemplo: Contar la cantidad de elementos que contiene una lista (hacer nuestro propio length)

;; contar: lista → número
;; Cuenta recursivamente la cantidad de elementos contenidos en una lista
(define (contar l)
(if (empty? l) 0
(+ 1 (contar (rest l)))
)
)

Observemos la evaluación de una expresión que usa ésta función en la lista anterior llamada l:


;; Evaluación
(contar l) → (contar (list ‘a ‘b ‘c))
(if (empty? (list ‘a ‘b ‘c)) 0
(+ 1 (contar (rest l)))
)
) →
(if (false) 0
(+ 1 (contar (rest l)))
)
) →
(+ 1 (contar (rest (list ‘a ‘b ‘c))) )

… después de reemplazar por la definición de (contar (rest l) ) (resto de una porción de la lista):

(+ 1 (+ 1 (+ 1 0) ) ) → (+ 1 (+ 1 1) ) → (+ 1 2) → 3

Lo anterior sugiere que  las listas exigen generalmente, funciones recursivas, pero éstas son de mucho cuidado. Un ejemplo clásico de recursividad es el factorial de n, que se define como
n!=n*(n-1)!
es decir, el factorial de 5 es 5*4! (se comprueba que, si 4!=4*3*2*1, osea que 5!= 5*4*3*2*1=5*4!)
Ejercicio: Definir en Scheme una función recursiva que halle el factorial de n:

(define (fact n)
(* n (fact (- n 1)))
)

La anterior definición parece bien escrita, sin embargo, quien la ejecute notará un problema: nunca termina. El factorial sólo se evalúa para n positivos y el caso base es cuando se pregunta por el factorial de 1 y la función anterior no incluye ese caso, por lo tanto nunca termina. Supongamos que se ejecuta la siguiente línea:

(fact 1) → (* 1 (fact -1) ) → (* 1 (* -1 (fact -2)))

… y así sucesivamente. Como se ve, la cola de ejecuciones recursivas sigue creciendo hasta que agota la memoria del PC.

La forma correcta de definir el factorial es:

(define (fact n)
(if (= n 1) 1
(* n (fact (- n 1)))
)
)

Ahora miremos cómo funcionaría para n=3.

(fact 3) → (* 3 (fact 2)) → (* 3 (* 2 (fact 1) ) )

en éste punto n = 1 y fact se convierte en el valor 1 y no se llama más a sí misma, por lo tanto la expresión final se evalúa:

(* 3 (* 2 1) ) → (* 3 2) → 6

Finalmente, para terminar con el ejemplo propuesto en la introducción, vamos a hacer la función que transfiere un estudiante a un profesor. De paso usaremos reglas de contexto local.

Ejemplo: Hacer una función que reciba una lista de estudiantes y un profesor y devuelva la lista de estudiantes asignados al profesor pasado como parámetro.


(define-struct estudiante (n a p no))
;; estudiante es una estructura, (make-estudiante n a p no), donde n, a y p son símbolos, no es un número
(define l (list
(make-estudiante 'cesar 'cabrera 'vargas 0)
(make-estudiante 'carlos 'perez 'cabrera 0)
(make-estudiante 'sandra 'sarria 'salgado 0)
)
)
;; transferir: lista-de-estudiantes, simbolo → lista-de-estudiantes
;; Crear una nueva lista de estudiantes cuyo componente profesor es igual a lo pasado en el segundo argumento.
(define (transferir l p)
(local (
(define ne (estudiante-n (first l)))
(define ae (estudiante-a (first l)))
(define noe (estudiante-no (first l)))
(define nuevo (make-estudiante ne ae p noe))
)
(if (empty? (rest l)) (cons nuevo empty)
(cons nuevo (transferir (rest l) p))
)
)
)
(transferir l 'rojas)

Ejercicio: Determinar si cierto estudiante está en la lista.

Conclusiones

Hemos explorado dos cosas muy potentes de Scheme: listas y recursividad. El paradigma funcional está fuertemente basado en recursividad y está diseñado para explotar al máximo esta técnica de iteración. Las listas por otro lado son la estructura más general posible y muchos lenguajes deben declarar estructuras complejas para soportarlas.