4 Definir Funciones
4.1 Metodología general
Cuando tiene que implementar una función que cumple cierto objetivo, es importante seguir los siguientes pasos, en este orden:
Entender lo que la función tiene que hacer.
Escribir su contrato, o sea, su tipo (cuántos parámetros, de qué tipo, qué retorna).
Escribir la descripción de la función en comentario.
Escribir los tests unitarios asociados a esta función, sobre los distintos posibles datos de entradas que pueda tener (casos significativos).
Finalmente, implementar el cuerpo de la función.
Es crucial dejar la implementación para lo último, especialmente, para después de definir los tests. Primero, escribir los tests le obliga a entender bien concretamente cómo se va a usar la función que necesitan definir. Segundo, hacer esto antes de la implementación asegura que sus tests están diseñados para evaluar la función en base a sus requerimientos, no en base a lo que acaba de implementar.
Para los tests, usaremos las funciones test y text/exn provistas por el lenguaje PLAY (ver Tests).
; double-list :: (Listof Number) -> (Listof Number) ; duplica los elementos de la lista (define (double-list l) (map (λ (x) (* x 2)) l)) (test (double-list '(1 2 3)) '(2 4 6)) (test (double-list empty) empty)
Note que el contrato de double-list indica que se tiene que pasar una lista de números. En el curso, asumiremos que los clientes respetan los contratos, por lo que no será necesario hacer este tipo de validación.
; double-list :: (Listof Number) -> (Listof Number) ; duplica los elementos de la lista ; lanza un error si el parámetro no es una lista (define (double-list l) (if (list? l) (map (λ (x) (* x 2)) l) (error "ERROR: not a list!!!!"))) (test (double-list '(1 2 3)) '(2 4 6)) (test (double-list empty) empty) (test/exn (double-list 4) "not a list")
Aquí hemos agregado un test que asegura que la función reacciona adecuadamente cuando uno pasa un argumento que no es una lista.
4.2 Procesar estructuras recursivas
4.2.1 Inducción
P(0): P es cierto para 0 (el caso inicial puede ser distinto según los casos).
P(n) ⇒ P(n+1): asumiendo P cierto para un n dado, demostrar que es cierto para el siguiente.
Resulta que hay una conexión directa muy fuerte entre esta herramienta lógica y la programación, especialmente cuando se trata de definir funciones que procesan datos recursivos.
Esta notación se llama BNF (Backus-Naur Form). Una especificación BNF es un sistema de reglas de derivación. Se usa mucho para describir gramáticas de lenguajes formales, pero no solamente.
| ‹nat› | ::= | 0 |
|
| | | ( add1 ‹nat› ) |
O sea, un natural es o 0, o el sucesor de un natural. El conjunto de los números naturales es el conjunto mínimo que cumple con ambas reglas (mínimo porque no contiene más elementos que aquellos obtenidos con esas reglas).
Por ende, el principio de inducción descrito anteriormente corresponde a esta definición: para establecer una propiedad sobre un natural n, hay que demostrarla para 0 y para el caso (add1 n). La occurrencia de ‹nat› en la segunda regla de derivación se conecta directamente con la hipótesis de inducción. O sea, para demostrar la propiedad para (add1 n), tenemos el derecho de asumir la propiedad para n. De manera equivalente, para demostrar la propiedad para n, tenemos el derecho de asumir la propiedad para (sub1 n).
4.2.2 Inducción y programación recursiva
Lo anterior se aplica directamente a la programación. Por ejemplo, si queremos determinar el factorial de n, podemos razonar por inducción, o sea, programar en forma recursiva:
(define (fact n) (if (zero? n) 1 (* n (fact (sub1 n)))))
Note como el cuerpo de la función sigue el mismo patrón que la gramática de ‹nat›. ¡Cualquier función que procesa un natural puede ser definida siguiendo ese patrón! El patrón es:
(define (f n) (if (zero? n) ... ; caso base ... (f (sub1 n)) ...)) ; paso inductivo
La llamada recursiva a (f (sub1 n)) corresponde al uso de la hipótesis de inducción (asumiendo el resultado de f para n-1). En la gramática, se nota la llamada recursiva porque ‹nat› esta definido en función de ‹nat›.
(define (even? n) (if (zero? n) #t (not (even? (sub1 n)))))
4.2.3 Inducción estructural y metodología
La idea de la inducción se generaliza a estructuras arbitrarias más complejas que <nat>. Se llama inducción estructural. A partir del momento en que pueden describir la gramática BNF de la estructura que su función esta procesando, ¡ya pueden definir "ciegamente" el template del cuerpo de la función!
Entendiendo la estructura del dato que procesa la función, escribir el patrón recursivo correspondiente.
Completar el cuerpo de la función, siguiendo el análisis por casos.
Gracias a esta metodología refinada, pueden tener la definición casi completa de su función (documentación, contrato, tests, y patrón recursivo) ¡sin ni siquiera haber empezado a programar lo específico de la función!
4.2.4 Pattern matching sobre estructuras recursivas
Una técnica tradicional para trabajar con estructuras de datos (incluyendo las recursivas) es el reconocimiento de patrones, más conocido en inglés como pattern matching. La idea es definir un caso para cada constructor de la estructura de datos, siguiendo así la gramática del mismo.
Racket tiene un soporte muy flexible para pattern matching sobre valores arbitrarios. Esta operación se realiza con la expresión match. Su forma de uso es:
(match target-expr [pattern expr ...+] ...)
Es decir, una expresión match está conformada por la expresión que queremos procesar, target-expr, y una o más cláusulas que corresponden a un patrón y una expresión. La semántica es similar a la de cond: se intenta hacer match de target-expr con cada patrón en forma secuencial, y se evalúa la expresión expr de la primera cláusula donde el matching es exitoso.
En la documentación de Racket se indica el uso básico de match. En general, cualquier valor literal puede ser matcheado:
> (match "hola" ["hola" 1] ["chao" 2]) 1
> (match (and #t #f) [#t "bueno"] [#f "malo"]) "malo"
En caso que ningún patrón coincida con la expresión, se genera un error:
> (match 1 [2 #t] [3 #f]) match: no matching clause for 1
Para definir un caso por defecto al final de la lista de patrones, puede usar el patrón [else ...] que siempre realiza matching (es posible usar cualquier identificador, pero por convención usaremos else). Por ejemplo:
> (match 1 [2 #t] [3 #f] [else #t]) #t
Note que por razones de eficiencia los números naturales no están definidos inductivamente en Racket. Por lo tanto la siguiente expresión produce un error al ser evaluada:
(match n [0 ...] [(add1 m) ...]) Como ejercicio, implemente la función even? usando match y el patrón app.
Además es posible hacer matching sobre los constructores de pares, listas y vectores; y sobre los constructores de estructuras arbitrarias. Racket provee un expresivo lenguaje de patrones, que puede consultar en la documentación.
El uso de pattern matching facilita de gran manera la programación, en particular para los intérpretes que desarrollaremos en el curso, y muestra claramente la conexión entre una estructura de datos recursiva y las operaciones que se realizan sobre ella. Por lo tanto, desde ahora en adelante y como regla general, usaremos pattern matching para procesar estructuras de datos.
4.3 Ejemplos
Esta sección muestra como se aplica la metodología anterior a través de múltiples ejemplos.
4.3.1 Procesar listas
Una lista puede ser descrita con la siguiente gramática BNF:
| ‹list› | ::= | (list) |
|
| | | ( cons ‹val› ‹list› ) |
| ‹val› | ::= | cualquier valor |
Por ende, el patrón de cualquier función que procesa listas es el siguiente:
(define (f l) (match l [(list) ...] ; caso base [(cons h t) ... h ... (f t) ...])) ; caso recursivo
El pattern matching sobre listas es pervasivo en distintos lenguajes funcionales. Dada una lista con cabeza (head) h y cola (tail) t, su patrón en ML es h::t, mientras que en Haskell es h:t.
Observe que usamos (list) para denotar el constructor de una lista vacía. También es posible utilizar el valor literal '(). Sin embargo, hay que tener cuidado y no usar el identificador empty, ya que a pesar de denotar una lista vacía, como se aprecia en este código:
> empty '()
> (eq? empty '()) #t
> (eq? empty (list)) #t
no es un constructor de esta estructura de datos, ni tampoco un valor literal. Recuerde que el lenguaje de patrones que hemos descrito hasta ahora sólo considera valores literales (como '()) y constructores (como list o cons). Al utilizar empty como patrón, éste se considera como un identificador librecuyo matching será siempre exitoso (al igual que else).
; length :: List -> Number ; retorna el largo de la lista (define (length l) (match l [(list) 0] [(cons h t) (+ 1 (length t))])) (test (length (list)) 0) (test (length '(1 2 3 4)) 4)
; contains? :: List Any -> Boolean ; determina si la lista contiene el elemento dado (define (contains? l v) (match l [(list) #f] [(cons h t) (or (equal? h v) (contains? t v))])) (test (contains? (list) 5) #f) (test (contains? '(1 2 3 4) 4) #t) (test (contains? '(1 2 3 4) 5) #f)
Ejercicios: defina las siguientes funciones que operan sobre listas: sum, reverse, map, foldl
4.3.2 Procesar árboles binarios
Un árbol binario es o una hoja (con un valor), o un nodo con un valor y dos hijos, que son árboles también. O sea, podemos describir un árbol binario con el siguiente BNF:
| ‹bt› | ::= | ‹val› |
|
| | | ( list ‹val› ‹bt› ‹bt› ) |
Aquí decidimos representar una hoja simplemente con el valor que contiene, y un nodo con una lista de tres elementos. Más adelante veremos una forma más abstracta de representar datos (ver Estructuras de datos).
Note que en la segunda regla de derivación, el no-terminal ‹bt› aparece dos veces. Esto se traduce en el patrón con dos llamadas recursivas:
(define (f bt) (match bt [(list val left-bt right-bt) ...(f left-bt)...(f right-bt)...] ; caso recursivo [val ...])) ; caso base
Observe que en esta definición de la estructura fue necesario aplicar el matching sobre el caso recursivo antes que sobre el caso base. La razón es que de lo contrario el patrón val aplicaría en todas las situaciones, pues simplemente asocia ese identificador con el valor sobre el cual se aplica. En el siguiente capítulo veremos que esta precaución ya no será necesaria para las estructuras desarrolladas en el curso.
; bt-contains? :: BinTree Any -> Boolean ; determina si el árbol contiene el elemento dado (define (bt-contains? bt v) (match bt [(list val left-bt right-bt) (or (equal? val v) (bt-contains? left-bt v) (bt-contains? right-bt v))] [val (equal? val v)])) (test (bt-contains? 3 3) #t) (test (bt-contains? 3 4) #f) (test (bt-contains? '(1 (2 3 4) (5 (6 7 8) 9)) 10) #f) (test (bt-contains? '(1 (2 3 4) (5 (6 7 8) 9)) 7) #t)
Ejercicios: defina las siguientes funciones que operan sobre árboles binarios: sum, max, map-bt, foldl-bt
4.3.3 Procesar listas anidadas
Para terminar, consideremos un ejemplo un poco más complicado: listas anidadas, o sea, listas que pueden contener otras listas. (Esto puede ser visto como una forma de representar árboles n-arios también.)
La gramática de las listas anidadas es:
| ‹nl› | ::= | (list) |
|
| | | ( cons ‹elem› ‹nl› ) |
| ‹elem› | ::= | ‹val› |
|
| | | ‹nl› |
A diferencia de los casos anteriores, tenemos un no-terminal más (‹elem›), en el cual una de las alternativas implica recursión. Esto implica un procesamiento "en profundidad" además de "en anchura". La idea sigue siendo la misma para definir el patrón:
En general, (? p) es un patrón que matchea si el predicado p es cierto para el valor. Aquí, (? list?) matchea si el valor es una lista.
(define (f l) (match l [(list) ...] ; caso base [(cons h t) (match h ; h puede ser <val> o <nl> [(? list?) ...(f h) ... (f t)...] ; <nl> [else ... (f t) ...])])) ; <val>
Observe que nuevamente se intenta primero el caso más específico ‹nl› antes del caso general ‹val›.
Por ejemplo:
; nl-contains? :: List Any -> Boolean ; determina si la lista contiene el elemento dado, recorriendo en profundidad (define (nl-contains? l v) (match l [(list) #f] [(cons h t) (match h [(? list?) (or (nl-contains? h v) (nl-contains? t v))] [else (or (equal? h v) (nl-contains? t v))])])) (test (nl-contains? (list) "hola") #f) (test (nl-contains? '(1 2 3 4) 3) #t) (test (nl-contains? '(1 2 3 4) 5) #f) (test (nl-contains? '(1 (2 3 () 4) (11 (((12))) (5 (6 7 8) 9))) 10) #f) (test (nl-contains? '(1 (2 3 () 4) (11 (((12))) (5 (6 7 8) 9))) 7) #t)
Note que en la definición anterior, es posible evitar repetir el mismo llamado recursivo (nl-contains? t v) sacando el or fuera del (match h ...):
(define (nl-contains? l v) (match l [(list) #f] [(cons h t) (or (match h [(? list?) (nl-contains? h v)] [else (equal? h v)]) (nl-contains? t v))]))
Ejercicios: defina las siguientes funciones que operan sobre listas anidadas: map*, foldl*, y max (usando foldl*).