Vamos al grano, o, como diría Haskell B. Curry, «let’s cut to the chase». Esto ya se puede hacer en AUSTRA (en cuanto libere la próxima versión):
let mcd(a, b: int): int =
let m = a % b in iff(m = 0, b, mcd(b, m)) in
mcd(80, 140)
Esta es una versión recursiva del máximo común divisor, calculado no con restas, sino con el módulo de la división. Observaciones importantes:
- Estoy declarando la función como una función local del script. Me falta permitir ahora la declaración de funciones como si fuesen definiciones paramétricas. No lo he hecho todavía porque la implementación de este tipo de funciones se realiza mediante lambdas, que se asignan a una variable local. La recursividad es posible porque la variable local está disponible, con toda la gloria de su prototipo, cuando se compila el cuerpo de la función. Cuando se trate de una definición, probablemente use un truco parecido, pero no es tan inmediato (internamente) como cuando defino una función como parte de una cláusula let.
- Como se trata de una función recursiva, observe que he definido su tipo de retorno explícitamente. Si no, cuando el compilador encuentre la llamada recursiva a mcd va a tener que volverse loco infiriendo cuál es el tipo de retorno. Ese tipo de inferencias es posible, pero ahora mismo el compilador no está preparado para ello. En mi defensa, recuerde que incluso el gran F# necesita el modificador rec para declarar funciones recursivas. Y F# sí es un lenguaje funcional con todas las de la ley.
- En este caso, hay una cláusula let anidada dentro de la definición de función. Austra tenía una regla para «aplanar» siempre estas cláusulas en el nivel superior, pero aquí me interesa violar la regla. Eso, o tengo que calcular dos veces el módulo de los dos parámetros.
Otro ejemplo de función recursiva, que utiliza también una cláusula let anidada, aunque esta vez, de tipo diferente:
let fact(n: int) =
let f(n, acc: int): int = iff(n <= 1, acc, f(n - 1, n * acc)) in
f(n, 1);
fact(10);
- Esta es la archifamosa función factorial, pero en vez de definirla en la forma más simple, la defino con una función auxiliar que permite recursividad "por la cola".
- Aunque el factorial es normalmente recursivo, esta vez no se llama a sí mismo, y no hay que declarar explícitamente el tipo de retorno.
- Por el contrario, la función interna f sí se llama a sí misma, y hay que tener cuidado con su prototipo.
Claro está que podemos declarar funciones sin tanta fanfarria. Por ejemplo, el factorial es mejor programarlo así:
let fact(n: int) = [x in 2..n].prod; fact(10);
Recuerde que empezamos con una secuencia de enteros, disfrazada de constructor de secuencias, por lo que no necesitamos poner los valores de la secuencia en un vector, ocupando memoria.
Por cierto, mire lo que podemos hacer ahora con las secuencias:
let collatz(n: int) =
iseq::unfold(1000000, n, x => iff(x % 2 = 0, x / 2, 3x + 1))
.until(x => x = 1);
collatz(137)
Esta función genera la secuencia de la conjetura de Collatz para el número entero suministrado como parámetro. Es un problema interesante, y aparentemente fácil, pero que aún no está resuelto. La novedad es que ahora Austra tiene un método Until y un método While que sirven para este tipo de acrobacias. Nuestra función mcd podría haberse también programado sin recursión, mezclando unfold con uno de estos métodos.