▼Pre  PLAI:   Scheme y Programación Funcional
►3 Programar con Funciones
On this page:
3.1 Funciones parametrizadas por funciones
3.2 Funciones anónimas
3.3 Funciones que producen funciones
    ← prev  up  next → 

3 Programar con Funciones

Éric Tanter

Hemos visto cómo usar funciones, pero no nos hemos preocupado de entender qué son las funciones en Scheme. Por ejemplo:
> +

#<procedure:+>

El mismo programa en C o Java daría un error, porque en estos lenguajes, las funciones (procedimientos, métodos) no son valores. La interacción anterior demuestra que en Scheme, al igual que en muchos lenguajes (ML, Haskell, Scala, Python, Clojure, etc.), las funciones sí son valores. Esta característica es una de las perlas de la programación funcional, dando luz a formas muy poderosas de componer programas.

3.1 Funciones parametrizadas por funciones

Dado que las funciones son valores, una función puede recibir a otra función como parámetro. Esto permite abstraer ciertos procesos. Por ejemplo, si uno quiere agregar 1 a todos los elementos de una lista, puede recorrer la lista y construir una nueva lista con los elementos incrementados. De igual manera, si uno quiere convertir todos los números de una lista en strings, tiene que recorrer la lista y aplicar la conversión a cada elemento. Este recorrido puede ser parametrizado por la función a aplicar a cada elemento. La función que hace esto se llama map:

(define my-list '(1 2 3 4 5))

 

> (map add1 my-list)

'(2 3 4 5 6)

> (map number->string my-list)

'("1" "2" "3" "4" "5")

Otro procesamiento típico de una lista de elementos es calcular un valor consolidado a partir de todos los elementos de la lista. Por ejemplo, sacar la suma de los elementos de una lista. O determinar cuál es el máximo de la lista.

> (foldl + 0 my-list)

15

> (foldl + 100 my-list)

115

> (foldl max 0 my-list)

5

foldl reduce una lista a un valor usando la función (de dos parámetros) que uno le pasa como primer parámetro. Parte aplicando esta función al primer elemento de la lista, usando como valor inicial el segundo parámetro (0 en el primer ejemplo). El resultado así obtenido es usado con el segundo elemento de la lista, y así sucesivamente. Como este recorrido procede de izquierda a derecha, se llama foldl, por fold (doblar) left. Existe la función foldr que procede al revés, partiendo con el último elemento de la lista.

fold(l/r) también es conocido como reduce en otros lenguajes (más precisamente, en general reduce es como foldl donde el valor inicial es el primer elemento de la lista). La composición de map y reduce es la base del framework MapReduce de Google, que es clave para el procesamiento escalable de consultas sobre grandes cantidades de datos.

Para entender bien la diferencia entre foldl y foldr, es instructivo detallar paso a paso la evaluación de los siguientes ejemplos:

(foldl + 0 '(1 2 3))
↦ (+ 3 (+ 2 (+ 1 0)))
↦ (+ 3 (+ 2 1))
↦ (+ 3 3)
↦ 6
 
(foldr + 0 '(1 2 3))
↦ (+ 1 (+ 2 (+ 3 0)))
↦ (+ 1 (+ 2 3))
↦ (+ 1 5)
↦ 6

Ejercicio: detalle paso a paso la evaluación de las siguientes expresiones, explicando así el resultado obtenido:
> (foldl cons '() my-list)

'(5 4 3 2 1)

> (foldr cons '() my-list)

'(1 2 3 4 5)

Hay muchas más funciones que reciben otras funciones. Las posibilidades son infinitas. Un ejemplo muy práctico también es seleccionar en una lista todos los elementos que cumplen cierta condición. Esto se hace con filter, pasandole un predicado como parámetro. También existe sort, parametrizado por una función de comparación.

> (filter even? my-list)

'(2 4)

> (sort my-list >)

'(5 4 3 2 1)

Programar de esa manera es mucho más declarativo y conciso que la programación imperativa tradicional. La clave está en el poder de abstracción que permite tener funciones (programas) como parámetros de otras funciones.

Ejercicio: estudie la documentación de las funciones para iterar, filtrar y buscar, y úselas sobre listas de su elección.

Ejercicio: defina, usando foldl, la función (reject lst pred) que retorna la lista de los elementos de la lista lst que no cumplen con el predicado pred.

3.2 Funciones anónimas

Como hemos visto, existe la función add1 que incrementa su parámetro:
> add1

#<procedure:add1>

> (add1 2)

3

Si bien esta función es útil, por ejemplo para pasarla como parámetro de map, uno podría preguntarse: ¿existe add2?
> add2

add2: undefined;

 cannot reference undefined identifier

No existe. Claramente se puede definir simplemente:
(define (add2 x) (+ x 2))

 

> (map add2 '(1 2 3))

'(3 4 5)

Similarmente, si necesitamos incrementar de 124 a todos los elementos de una lista, podemos definir add124. Sin embargo, tener que darle un nombre a tal función es un poco artificial, dado que es muy probable que no la necesitemos más adelante.

En Scheme, uno puede definir una función anónima usando la forma sintáctica lambda. Por ejemplo:
> (lambda (x) (+ x 124))

#<procedure>

Como vemos, una función anónima así definida es también un valor. Por lo que se puede pasar como parámetro (usamos la notación λ (ctrl-\) por estética):
> (map (λ (x) (+ x 124)) '(1 2 3))

'(125 126 127)

> (foldl (λ (x y) (and x y)) #t '(a b c d #f e))

#f

Ahora que sabemos crear funciones anónimas, podemos entender que la forma para definir funciones que vimos antes:

(define (foo x) x)

no es nada más que azúcar sintáctico para la definición de un identificador asociado a la lambda correspondiente:

(define foo (λ (x) x))

También se puede introducir funciones con nombre local:

> (let ([f (λ (x) x)])
    (f 10))

10

> f

f: undefined;

 cannot reference undefined identifier

Para introducir una función local que es recursiva (es decir, que se llama a sí misma), hay que usar letrec:
> (letrec ([fact (λ (n)
                   (if (< n 2) 1
                       (* n (fact (sub1 n)))))])
    (fact 10))

3628800

(¿Qué pasa si uno usa let y no letrec?)

Ejercicio: use la función findf para buscar el primer elemento múltiplo de 13 en una lista dada (retorna #f si no hay); defina el predicado como una función anónima. Puede usar la función modulo.

3.3 Funciones que producen funciones

Tener la posibilidad de crear funciones anónimas en cualquier parte permite hacer algo sumamente poderoso: definir funciones que crean otras funciones. O sea, generadores de funciones. Por ejemplo, volviendo a nuestras funciones add1, add2, add124, vemos que sus definiciones son muy similares. Lo único que cambia es el número usado en la suma con el parámetro.

Podemos ahora definir una única función addn que es capaz de fabricar una de esas funciones:

(define (addn n)
  (λ (x)
    (+ x n)))

Con addn podemos crear y nombrar los variantes que queremos:
(define add10 (addn 10))
(define add124 (addn 124))

 

> (add10 12)

22

> (map add124 my-list)

'(125 126 127 128 129)

Y también podemos crear una función y usarla directamente, sin nombrarla:
> (map (addn 20) my-list)

'(21 22 23 24 25)

Aquí va un último ejemplo:
(define (more-than n)
 (λ (m)
   (> m n)))

 

> (filter (more-than 10) '(13 2 31 45 9 10))

'(13 31 45)

> (filter (more-than 20) '(13 2 31 45 9 10))

'(31 45)

Esa capacidad de crear dinámicamente funciones similares pero con atributos propios (por ejemplo, el valor de n en las distintas funciones creadas por addn) es muy similar a la creación de objetos a partir de clases en Java. Volveremos a explorar esta conexión en el OOPLAI.

Ejercicio: defina la función (negate pred) que retorna un predicado que es la negación de pred.

Ejercicio: use negate y filter para definir la función (reject lst pred) (que vimos anteriormente) de manera más concisa aún.

Esta técnica se llama currificación (currying)

Ejercicio: defina la función (curry f) que, dado una función de tipo (A B → C), retorna una función equivalente de tipo A → (B → C). Es decir, permite que una función que toma dos parámetros los tome uno por uno. Ejemplo
> (define cons1 ((curry cons) 1))
> (map cons1 '(a b c d))

'((1 . a) (1 . b) (1 . c) (1 . d))

Esta técnica se llama memoization.

Ejercicio: defina la función (memoize f) que, dado una función de tipo (A → B), retorna una función equivalente que mantiene un cache <argumento → valor>. Para el cache, use una tabla de hash.

    ← prev  up  next →