Funciones de orden superior

Tanto en matemáticas como en informática, las funciones de orden superior son aquellas que cumplen, al menos, una de estas condiciones:

  1. Esperan como argumento/s una o más funciones.
  2. Devuelven una función como resultado.

Ejemplos en matemáticas son la derivada y la antiderivada o función primitiva.

operador diferencial

El operador diferencial es una función de orden superior

Antiderivada

La antiderivada de una función f es una función F tal que F’ = f

En informática son la esencia de los lenguajes funcionales, pero también aparecen en lenguajes de otros paradigmas. Este es un ejemplo en el lenguaje Scheme en el que la función (f x) recibe un argumento y devuelve una función:

(define (f x)
  (lambda (y) (+ x y)))
(display ((f 3) 7))

Puede ejecutarse aquí para ver el resultado.

Cuando nació Javascript, a algunos programadores les pareció un lenguaje orientado a objetos fallido1, sobretodo porque, por razones comerciales, se le puso un nombre que lo asocia con Java. Desconozco si su creador estuvo muy de acuerdo con ese nombre pues, tal y como se diseño este lenguaje, da bastante juego a la programación funcional. En el siguiente ejemplo, el método filter() es una función de orden superior, pues espera recibir una función como parámetro:

function isPrime(x){
  if (x === 2) {
     return true;
  }
  let test = x%2 !== 0;
  let i = 3;
  stop = Math.floor(Math.sqrt(x)); // Raíz entera de x
  while (test && i <= stop) {
	  test = x%i !== 0;
	  i = i + 2;
  }
  return test;
}

const numbers = [47, 139, 137, 213, 2, 3, 45, 1515];
const primeNumbers = numbers.filter(isPrime);
console.log(primeNumbers);

Lo que este programa hace es filtrar la formación de números naturales “numbers“, dejando sólo los que sean primos en “primeNumbers“. Cada elemento de “numbers” será evaluado por la función “isPrime” mediante la criba de Eratóstenes. El lector puede ejecutarlo accediendo a la consola del navegador pulsando F12 y modificar el valor de “numbers” con los números (o el número) que quiera saber si son primos o no.

Este tipo de funciones están en prácticamente todos los lenguajes modernos, incluso en los que no se tuvo en cuenta el paradigma funcional en el momento de su creación. Es el caso de PHP, donde podemos encontrar una gran cantidad de funciones que esperan otra función, como es el caso de, por ejemplo, preg_replace_callback()2:

$capitalice = function($coincidencia) {
    return strtoupper($coincidencia[1]);
};

echo preg_replace_callback('~-([a-z])~', $capitalice, 'hola-mundo');

Además de usar las implementadas en funciones y métodos propios del lenguaje, también podemos crear las nuestras, de forma parecida a un lenguaje completamente funcional. En Javascript, la Wikipedia nos ofrece el siguiente ejemplo:

const twice = (f, v) => f(f(v));
const add3 = v => v + 3;

console.log(twice(add3, 7));

Lo mismo es posible en PHP:

$twice = function($f, $v) {
    return $f($f($v));
};

$f = function($v) {
    return $v + 3;
};

echo($twice($f, 7));

La programación funcional pretende tratar la programación como la evaluación de funciones matemáticas, paradigma muy diferente a la programación imperativa, basada en estados y en instrucciones que lo cambian. Tal vez las características funcionales que tienen algunos lenguajes puedan ayudarnos a introducirnos en un paradigma, el funcional, que nos exige una forma muy distinta de enfocar los problemas.


 

1 Todavía hoy en día, y a pesar de los cambios que ha sufrido en los últimos ECMA, sigue despertando las críticas de los programadores que, debido a su nombre, esperan que se comporte como un lenguaje completamente orientado a objetos, como Java, y se dan de bruces contra la realidad.

2 El parámetro que recibe la función contenida en $capitalize son las coincidencias que encuentre la expresión regular.

No es recursivo todo lo que parece.

En la entrada anterior hablé sobre la recursividad mediante Scheme y la función de Ackermann. Hay algo curioso, o al menos a mi me sorprende, sobre Scheme y es como interpreta como iterativos algoritmos aparentemente recursivos. Como ejemplo 2 algoritmos para calcular los números de Fibonacci, uno recursivo y el otro iterativo aunque parezca recursivo. Primero recordar que estos números de definen así:

0 Si n = 0

1 Si n = 1

Fib(n – 1) + Fib(n – 2) Si n ≠ 0 y n ≠ 1

Esta definición lleva directamente a este algoritmo recursivo en Scheme:

(define (fib n)
    (cond ((= n 0) 0)
    ((= n 1) 1)
    (else (+ (fib (- n 1))
        (fib (- n 2))))))

Funciona pero es poco eficiente, la complejidad aumenta exponencialmente a medida que el número que buscamos, n, es mayor, pues se trata de recursividad en árbol. Este otro algoritmo es mucho más eficiente:

(define (fib n)
    (fib-iter 1 0 n))

(define (fib-iter a b count)
    (if (= count 0)
    b
    (fib-iter (+ a b) a (- count 1))))

Si queremos saber el Fibonacci para 4 lo invocamos así:

(fib 4)

Y hará:

(fib 4)

(fib-iter 1 0 4)

(fib-iter 1 1 3)

(fib-iter 2 1 2)

(fib-iter 3 2 1)

(fib-iter 5 3 0)

3

Scheme lo ejecuta como iterativo, no como recursivo. ¿Pero que sucede si implementamos ese mismo algoritmo en un lenguaje tipo procedimental como C o Pascal? Veamos como podría ser en PHP, el rey de la web:

function fib ($a, $b, $aCalc) {

    if ($aCalc == 0) {
        return $b;
    }else{
        $aCalc--;
        fib($a + $b, $a, $aCalc);
    }
}

$result = fib (1, 0, 4);
echo $result;

Y no funcionará. ¿Por qué? Pues porque PHP lo interpretará como recursivo, no como iterativo, y hará:

(fib 1 0 4)

(fib 1 0 4)(fib 1 1 3)

(fib 1 0 4)(fib 1 1 3)(fib 2 1 2)

(fib 1 0 4)(fib 1 1 3)(fib 2 1 2)(fib 3 2 1)

(fib 1 0 4)(fib 1 1 3)(fib 2 1 2)(fib 3 2 1)(fib 5 3 0)

Pero en vez de quedarse aquí empezará a hacer los “returns”, los “pops” de la pila:

(fib 1 0 4)(fib 1 1 3)(fib 2 1 2)(fib 3 2 0)

(fib 1 0 4)(fib 1 1 3)(fib 2 1 1)

(fib 1 0 4)(fib 1 1 2)

(fib 1 0 3)

:-/

Entonces, ¿como hacer “entender” al compilador o intérprete en este tipo de lenguajes que deseamos una implementación iterativa? La única opción es hacer servir las instrucciones que disponen para bucles: while, for, repeat, etc. Este podría ser un ejemplo en PHP:

function fibonacci($n) {
    $f[0] = 0;
    $f[1] = 1;

    for ($i = 2; $i <= $n; $i++) {
        $f[$i] = $f[$i-1] + $f[$i-2];
    }

    echo $f[$n];
}
fibonacci(8);

Ésta curiosidad se puede expresar también a la inversa: Scheme interpreta como iterativos algoritmos que a quienes estamos acostumbrados a los lenguajes por preocedimientos (procedural languages) nos parecen iterativos. Probablemente ésta es mejor forma de expresarlo.

La función de Ackermann

Llevo un par de meses bastante entretenido con el libro del MIT “Structure and Interpretation of Computer Programs”. Si bien el MIT nos permite el acceso gratuitamente a todo su contenido aquí, es un libro genial que realmente vale la pena comprárselo.

En uno de sus primeros capítulos, donde se contrastan los procesos iterativos con los recursivos y como aquel que no quiere la cosa, en un ejercicio aparentemente inocente aparece un procedimiento que computa una variante de la función matemática de Ackermann:

(define (A x y)
    (cond ((= y 0) 0)
    ((= x 0) (* 2 y))
    ((= y 1) 2)
    (else (A (- x 1)
        (A x (- y 1))))))

Dicha función es famosa en teoría de la computación. Lo que sorprende de dicha función, a diferencia de las que habitualmente se usan como función “modelo” para enseñar qué es la recursividad, es que no es recursiva primitiva. El ejemplo típico de la función recursiva es la que nos da el factorial de un número n:

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

El proceso que seguiría para calcular por ejemplo el factorial de 6 sería:

factorial(6)

6 * factorial(5)

6 * (5 * factorial(4))

6 * (5 * (4 * factorial(3)))

6 * (5 * (4 * (3 * factorial(2))))

6 * (5 * (4 * (3 * (2 * factorial(1)))))

Este es el punto en que más se carga la pila, a partir de aquí serían “pops”:

6 * (5 * (4 * (3 * (2 * 1))))

6 * (5 * (4 * (3 * 2)))

6 * (5 * (4 * 6))

6 * (5 * (24))

6 * (120)

720

Las funciones recursivas “típicas” siguen éste patrón, se van sumergiendo hasta llegar a un punto de inflexión a partir del cual van emergiendo hasta aflorar el resultado final. La función de Ackermann podría parecer que transcurre igual, por ejemplo (A 1 6) sería:

(A 1 6)

(A 0 (A 1 5))

(A 0 (A 0 (A 1 4)))

(A 0 (A 0 (A 0 (A 1 3))))

(A 0 (A 0 (A 0 (A 0 (A 1 2)))))

(A 0 (A 0 (A 0 (A 0 (A 0 (A 1 1))))))

(A 0 (A 0 (A 0 (A 0 (A 0 2)))))

(A 0 (A 0 (A 0 (A 0 4))))

(A 0 (A 0 (A 0 8)))

(A 0 (A 0 16))

(A 0  32)

64

Es decir, 26 De hecho, para todo (A 1 n) el resultado siempre será 2n Pero veamos por ejemplo como transcurre al calcular (A 2 4):

(A 2 4)

(A 1 (A 2 3))

(A 1 (A 1 (A 2 2)))

(A 1 (A 1 (A 1 (A 2 1))))

(A 1 (A 1 (A 1 2)))

(A 1 (A 1 (A 0 (A 1 1))))

(A 1 (A 1 (A 0 2)))

(A 1 (A 1 4))

(A 1 (A 0 (A 1 3)))

Como se puede observar, se va profundizando para después emerger y a continuación volver a sumergirse. Después de un largo proceso recursivo, el resultado final que acaba dando es 65536, es decir, 216.