En la entrada de hoy, «Notas de programación funcional», describiré ciertos conceptos generales de la programación funcional. Serán pequeñas píldoras documentales, o bien, mis notas sobre los conceptos iniciales en la programación funcional. No pretendo realizar definiciones formales, ni que la entrada sea formal; solo pretendo crear pequeñas notas las cuáles sirvan para allanar los primeros pasos en el estudio de la programación funcional.
El lenguaje Scala es un lenguaje híbrido con en el que se aplican dos paradigmas: el paradigma funcional y el paradigma orientado a objetos. El creador del lenguaje es Martin Odersky en el 2004. El lenguaje Scala está basado en el lenguaje Haskell y el lenguaje Erlang, adquiriendo de estos dos lenguajes, lo mejor de ellos. Del lenguaje Haskell, los principios de la programación funcional y, del lenguaje Erlang, el modelo de actores para la programación concurrente.
Funciones
En Scala hay diferentes tipos de funciones: funciones totales, funciones parciales, first class function,…No voy a realizar una descripción total de todas ellas, pero me centraré en el concepto de función genérico.
Definimos una función con la siguiente estructura:
def nombreFunción([lista de parámetros]): [Tipo de retorno] = {
Cuerpo de la función
return [expresiónRetorno]
}
Un ejemplo de función es la siguiente:
def suma( operador1:Int, operador2:Int ): Int = {
var suma: Int = 0
suma = operador1 + operador2
return suma
}
En Scala, tenemos la posibilidad de definir funciones como variables, sin la necesidad de definir una función de forma específica; este caso, se conoce como first class function. Un ejemplo de first class function es el siguiente:
val suma: (Int,Int) => Int = (a:Int, b:Int) => a + b
println(s"suma(2,3)=${suma(2,3)}")
println
El compilador Scala, realiza la transformación de la función suma como una clase de tipo Function, permitiendo la posibilidad de definir este tipo de variables función de forma sencilla.
Las funciones parciales son aquellas funciones en donde se define parte de la función. En el siguiente ejemplo, defino una función parcial suma en donde se define el primer operando y, el segundo operando, es pasado por parámetro.
val suma2: PartialFunction[Int, Int] = {
case d:Int => 2 + d
}
println(s"suma2(2+3)=${suma2(3)}")
println
Recursividad
La recursividad es aquella forma en la cual una función se define basada en su propia definición. Una función recursiva se define en función de dos pasos: el caso base, solución a la instancia mas sencilla; y, el caso de inducción, solución a los casos complejos.
Un ejemplo típico de recursividad es la función factorial, la cual se define en lenguaje Scala como sigue:
def factorial(n: Int): Int = {
if (n > 1)
n * factorial(n-1)
else
1
}
println(s"factorial(3)=${factorial(3)}")
println
Las funciones recursivas son utilizas en estructuras de datos recursivas, como por ejemplo, una lista o un árbol.
Existe dos tipos de recursividad: la recursividad por la cabecera y la recursividad por la cola.
La recursividad por la cabecera es aquella recursividad que se realiza aplicando el cálculo de la operación con la cabecera de la estructura y, una vez realizada, se realiza la llamada recursiva con la cola. Con esta recursividad, para el caso de una lista, se realiza el recorrido desde el inicio de la estructura (cabecera) hasta el final de la lista.
La recursividad por la cola es aquella recursividad que se realiza aplicando las llamadas recursivas a la función y, una vez llamadas, se realiza el cálculo; es decir, recorres la lista con las llamadas y, en el retorno de la recursividad, aplicas el cálculo. Con esta recursividad, para el caso de una lista, se realiza el recorrido desde el final de la estructura hasta el inicio.
ADT
Scala es un lenguaje tipado, como por ejemplo: tipo entero, Int; tipo alfanumérico, String; tipo lógico, Boolean;… Con la combinación de estos tipos, podemos definir tipos más complejos, mediante las operaciones suma y producto.
Definimos un ADT (Algebraic Data Type), tipo de datos algebraico, como aquel tipo conformado por tipos simples los cuales, mediante las operaciones de suma y producto, formamos tipos más complejos. La operación suma es aquella operación que corresponde con la herencia y, la operación producto, es aquella operación que corresponde con las definiciones de los parámetros de las case class.
Un ejemplo de un ADT que define un tipo Lista con tipos enteros, es el siguiente:
sealed trait MiLista
case class Null extends MiLista
case class Nodo(cabeza:Int, cola:MiLista)
De la definición anterior, podemos decir que tenemos la definición de una estructura de tipo lista de enteros de una forma matemática clara y sencilla; pero, ¿y si queremos definir una lista de otro tipo? La primera solución, es definir otro ADT para el tipo seleccionado; y, la segunda solución, consiste en definir un ADT con la capacidad de soportar polimosfirmo paramétrico. Un ejemplo de una lista con polimorfísmo paramétrico es el siguiente:
sealed trait MiLista[T]
case class Null[T]() extends MiLista[T]
case class Nodo[T](cabeza:[T], cola:MiLista[T])
Con la definición anterior, podemos definir una lista de cualquier tipo.
Funciones de Orden Superior (HOF – Hight Order Function)
Las funciones de orden superior son aquellas funciones que permiten definir como parámetro otra función, es decir, un parámetro de la función puede ser una función. Un ejemplo básico y sencillo de función HOF, puede ser el siguiente:
def ejemploHOF(mensaje:String, f: (Int,Int) => Int, operador1:Int, operador2:Int ): Unit = {
println(mensaje + "=" + f(operador1, operador2))
}
ejemploHOF( "Resultado de la suma(2,3)", suma, 2, 3 )
La salida por consola del ejemplo es el siguiente:
Resultado de la suma(2,3)=5
El ejemplo parece sencillo pero a partir de este concepto se construyen muchos patrones de la programación funcional que no son tan sencillos.
Catamorfismo
En los apartados anteriores describí conceptos como los ADT’s y funciones de orden superior; pero, llegado a este punto, hay que preguntarse: ¿cómo trabajo con los ADT’s?, ¿cómo realizo un cálculo sobre un ADT?, ¿con qué mecanismos los puedo manipular? La respuesta es sencilla, trabajamos los ADT’s con los catamorfismos.
Definimos catamorfismo como aquella formar de interpretar, manipular o consumir un ADT. Se puede definir con cualquier ADT y, a nivel práctico, se corresponde con la función fold.
El ADT es aquel tipo definido desde un punto de vista matemático y, la programación funcional, tiene un aspecto matemático; con lo cual, la forma de pensar debe de ser matemática.
Sea el ADT que define la estructura Lista del apartado anterior definido de la siguiente forma:
sealed trait MiLista[T] // Caso abstracto
case class Null[T]() extends MiLista[T] // Caso Base
case class Nodo[T](cabeza:[T], cola:MiLista[T]) extends MiLista[T]// Caso de Inducción
A nivel conceptual, una lista se puede representar con la anterior definición de la siguiente forma:
Lista(1,2,3) => val lista: MiLista[Int] = Nodo(1, Nodo(2, Nodo(3, Null) ) )
Dado el siguiente problema a resolver: cálculo de la suma de los elementos de una lista, es decir: dada un elemento de tipo MiLista[Int], se desea definir una función que calcule la suma de los elementos y retorne un número entero.
La definición del ADT está formada por tres elementos: caso base, caso de inducción y caso abstracto. Con estos tres casos definimos el catamorfismo de la siguiente forma:
- Caso Base. Dado un elemento de tipo Null[Int], ¿qué tengo que realizar para retornar como resultado un entero(B)?.
Null[Int] ---(B)---> Int; Resultado: B=0
Dado el caso base, tenemos que retornar el valor 0. Para toda lista vacía, la suma de los elementos de una lista es cero.
- Caso de inducción. Dado un elemento de tipo Nodo[Int], ¿qué tengo que realizar para calcular la suma de sus elementos(B)?
Node[Int] -----(A:Int, B:MiLista[Int]) => B(Int)---> Int; Resultado: (A, B) => B
Un Node está formado por una cabeza(parte A) y un cola de tipo MiLista(parte B). La suma de la parte A y de la parte B tiene que tener como resultado un número B entero, es decir, todo elemento A mas B (resultado de la cola) tiene que tener como resultado B
- Caso abstracto. El caso abstracto lo forma la unión del caso base y el caso de inducción; es decir, la operación suma y la operación producto. Así, tenemos:
- caso base: Null[Int] => B
- caso inducción: Nodo[T](cabeza:[T], cola:MiLista[T]); (A, B) => B
- caso abstracto: caso base más caso inducción: Null[Int] U Nodo[T](cabeza:[T], cola:MiLista[T]) => (B, (A,B)=> B)
Así, la función fold queda definida de la siguiente forma:
def fold[A,B](lista:MiLista[A])(base:B, f: (A, B) => B): B = lista match{
case Null() => base
case Nodo(h,t) => f(h, fold(t)(base,f))
}
Fold, FoldRight
La función fold es idéntica a la función foldRight. Estas funciones están enfocadas a una recursividad de cabacera.
Así, la función foldRight queda definida como sigue:
def foldRight[A, B](lista: MiLista[A])(zero: B,f: (A, B) => B): B = lista match {
case Nil => zero
case head::tail => f(head, foldRight(tail)(zero,f))
}
Desde un punto de vista de las llamadas a realizar y qué elementos intervienen en cada una de las llamadas, se puede ver como sigue:
-> 1 + foldRight(–)
-> 1 + (2 + foldRight(–) )
-> 1 + (2 + (3 + foldRight(–) ) )
-> 1 + (2 + (3 + ( 4 + foldRight(–) ) ) )
Por cada llamada, se van insertando una entrada en la pila del sistema. Cuando se termina el espacio, la ejecución falla. Un ejemplo para llegar a esta situación es el siguiente:
val listaEnteros = (1 to 325000).toList
println( foldRight(listaEnteros)(0, (a:Int, b:Int) => a + b) )
La salida por consola es la siguiente:
Exception in thread "main" java.lang.StackOverflowError
FoldLeft
La función foldLeft tiene un parecido con las funciones fold y foldRight, la diferencia, reside en el orden de los parámetros de la función pasada por parámetro. El tipo de recursividad es por la cola, es decir, se realiza la llamada recursiva y, una vez llamada, se realiza el cálculo. La función foldLeft se define como sigue:
@annotation.tailrec
def foldLeft[A,B](l:List[A])(zero:B, f:(B,A)=>B): B = l match {
case Nil => zero
case head::tail => foldLeft(tail)( f(zero,head), f )
}
Este tipo de recursión en Scala es la más eficiente porque se llama a la función con el valor acumulado.
Para demostrar la eficiencia de esta función, realizamos el cálculo de la suma de la lista de ejemplo de foldRight.
val listaEnteros = (1 to 325000).toList
println( foldLeft(listaEnteros)(0, (a:Int, b:Int) => a + b) )
La salida por consola es la siguiente:
1273054948
Como he comentado al inicio de la entrada, no he querido ser formal, simplemente he querido mostrar pequeñas píldoras documentales para que, a la persona iniciada en la programación funcional, le permita comprender las piedras iniciales. Desde mi experiencia, pasadas estas primeras piedras, el proceso de comprensión del resto de conceptos es más sencillo.
Álvaro Monsalve Serrano 