Archive for the 'Scala' category

Estudio función factorial en scala – Revisión funcional

feb 07 2012 Published by under Scala

Como programador de python que todavía anda algo despistado estudiando scala, ahora empiezo a captar la filosófía que hay detrás de este lenguaje de programación. Mientras que python empienza a erradicar poco a poco la programación funcional, en scala su influencia es cada vez mayor hasta el extremo de considerar precindibles la mayoría de los bucles. Aún asi, ambos lenguajes soportan la “compresión de listas” como técnica a medio camino entre funcional y bucle estándar, aunque esta técnica está más orientada a obtener listas a partir de otras listas, y no para realizar cálculos sobre un conjunto de números.

Voy a completar el anterior artículo que trataba del “Estudio función factorial en scala” con algunas formas más “funcionales” de definir el factorial:

La forma más simple de definir la función factorial:

def fact(n:Int) = (1 to n).product

En realidad, 1 to n no es un elemento sintáctico del lenguaje, si no más bien la forma alternativa de escribir la invocación del método 1.to(n). Este método nos genera una secuencia de números desde el 1 al n (equivalente en python a range(1,n+1)).

Curiosamente, también está definido fact(0) gracias a que product da como resultado el elemento neutro 1 en secuencias vacías 1.

Esta forma concisa de calcular el producto es común a todas las secuencias en scala. Faltaría, tan sólo, que operara con BigInts para que fuera perfecta:

def fact(n:Int) = (BigInt(1) to n).product

No es necesario indicar el tipo devuelto por la función puesto que el compilador es capaz de inferirlo de la expresión.

Otra forma funcional sería usando el método reduce, donde se indica explícitamente la operación binaria a realizar entre pares de elementos:

def fact(n:Int) = (BigInt(1) to n).reduce(_*_)

Como operación se pone una especie de plantilla (pattern) que representa la operación binaria de multiplicación. Por comparar, en python se puede hacer algo así:

from operator import __mul__

def fact(n):
   return reduce(__mul__, xrange(1,n+1))

Lamentablemente, el operador funcional 'reduce' está desapareciendo de python por considerarlo complejo de entender en su funcionamiento 2.

Por último, aún existe otra forma funcional de expresar el factorial en scala. Son los “plegados” (folds), similar en funcionamiento a reduce, pero con control sobre la dirección del recorrido y la posibilidad de dar un valor inicial:

def fact(n:Int) = (1 to n).foldLeft(BigInt(1))(_*_)

Seguro que pronto se me ocurrirán más formas.

  1. En el caso del método sum daría el elemento neutro para la suma, o sea, el 0. ↩

  2. Personalmente, considero que la desaparición de la programación funcional se debe más a la corta visión de quién sólo ve un encadenamiento de sentencias, en lugar de ver “actores” interaccionando en libre concurrencia. ↩

No responses yet

Estudio función factorial en scala

oct 17 2011 Published by under Scala

Como continuación al artículo que dediqué al estudio del factorial, voy a explicar cómo se haría este famoso algoritmo usando scala. Tengo que añadir que tan sólo llevo una semana con el lenguaje scala, por lo que es muy probable que haya algún aspecto de este lenguaje que me haya dejado por el camino.

Versión recursiva (y one-line)

La forma básica de la función sería:

def fact(n:Int):BigInt =
    if (n==0) 1
    else n*fact(n-1)

Si se compara con la función recursiva en python, no parece que haya mucha diferencia, con excepción de que en scala existe el tipado de datos.

Esta función es en realidad una sóla línea, por lo que podíamos haberla escrito de esta manera:

def fact(n:Int):BigInt = if (n==0) 1 else n*fact(n-1)

Es una clara señal de la orientación funcional que tiene scala.

Al igual que python, esta función recursiva se corta cuando se sobrepasa un cierto límite de llamadas recursivas para proteger la memoria del sistema.

El compilador de Scala posee una optimización especial denominda de “LLamada Terminal” (Tail Call)1 (optimización que no existe en JVM). Este tipo de optimizaciones son posibles cuando la última línea a ejecutar de la función es únicamente la llamada recursiva a sí misma, con lo cuál hace innecesario guardar el stack de ejecución puesto que no quedarían más líneas para ejecutar.

Para que sea posible aplicar esta optimización de “llamada terminal”, tenemos que reescribir nuestra función de modo que la última línea sea una llamada a sí misma. Para ello usaremos una función acumuladora que se encargue de realizar la multiplicación previamente a la llamada. Casi mejor si vemos el código:

def fact(n:Int):BigInt = {
    def factAcc(n:Int, acc:BigInt):BigInt =
        if (n<=1) acc else factAcc(n-1, n*acc)

    factAcc(n,1)
}

En las últimas versiones de scala existe una “anotación” especial para indicar al compilador de scala que intente aplicar la optimización de “LLamada Terminal”, o que nos dé un aviso de no poder hacerlo. Finalmente, así quedaría el código de nuestra función recursiva:

import scala.annotation.tailrec

def fact(n:Int):BigInt = {
    @tailrec
    def factAcc(n:Int, acc:BigInt):BigInt=
        if (n<=1) acc else factAcc(n-1, n*acc)

    factAcc(n,1)
}

Versión iterativa

Es la versión más sencilla:

def fact(n:Int):BigInt = {
    var res=BigInt(1)
    for (i <- 1 to n)
        res*=i
    res
}

Fórmula de Stirling

Para completar el estudio, podemos ver cómo sería la función de Stiling en Scala, bastante similar, como puede verse, a su versión en python:

import math._

def fact(n:Int):Double =
    sqrt(2*Pi*n)*pow(n/E,n)

  1. Existe algún intento para implementar esta optimización de “Tail Call” en python, con algunos decoradores más o menos funcionales. Si quieres ver motivos en contra, visita el artículo que escribió Guido sobre el tema: http://neopythonic.blogspot.com/2009/04/tail-recursion-elimination.html ↩

One response so far