Programación Funcional

Características Principales

• No hay efectos laterales: Una función siempre devuelve el mismo resultado para los mismos argumentos de entrada.
• Funciones como ciudadanos de primera clase:
  1. Una función puede ser pasada como argumento (Orden superior).
  2. Una función puede ser devuelta como resultado de la computación (Aplicación parcial).
• Tipos y estructuras de datos de usuario

Aplicación Parcial

La aplicación parcial permite invocar una función con un número de argumentos menor que el de parámetros de su definición. Esto es posible gracias a la currificación.

Estrategias de Evaluación

• Impaciente (Eager): Los argumentos se evalúan antes de llamar a la función, similar al paso por valor. Puede que no siempre termine la evaluación.
• Perezosa (Lazy): Siempre se llama a la función y se le pasan los argumentos. Garantiza la terminación siempre que sea posible. Similar al paso por necesidad.

Tipos Algebraicos

• Se definen usando data: data Estado = Casado | Soltero
• type crea sinónimos de tipos existentes.
• data crea nuevos tipos.
• Los constructores de datos son símbolos terminales.
• Los constructores de tipo son símbolos no terminales.

Los valores solo pueden contener constructores de datos. Los patrones (conjuntos de valores) contienen constructores de datos y también variables.

Ajuste de Patrones (Pattern Matching)

Una expresión e se ajusta a un patrón p si e puede verse como una concreción de p dando valores a las variables de p. El ajuste de patrones es un mecanismo habitual para definir funciones en programas funcionales.

Tuplas

Una tupla es un tipo de datos compuesto cuyas componentes pueden tener distintos tipos. Se definen usando type: type x... No se usa data porque no estamos creando un nuevo tipo, sino un sinónimo.

Listas

• Los Strings son listas de caracteres.
• La función show hace un casting a String.
• En Haskell, las listas son asociativas por la derecha. Se pueden crear listas intensionales: [x*x | x <- [1..5], odd x]
• Los generadores actúan de izquierda a derecha.

En un data la igualdad no está definida por defecto.

Coerción

La coerción es explícita y se realiza mediante funciones que transforman un tipo en otro.

Genericidad

Una función es genérica si su tipo es polimórfico.

Sobrecarga

La sobrecarga se implementa a través del concepto de clase de tipo. El sistema de clases de Haskell permite utilizar parametrización para definir funciones sobrecargadas, imponiendo a los tipos la condición de pertenecer a una clase.

La declaración de una clase de tipo (class) especifica las operaciones que debe implementar cualquier tipo que pertenezca o sea instancia de esa clase. Una función sobrecargada recibe implícitamente en su tipo el contexto apropiado.

Instancias

Instance permite introducir un tipo de datos en una clase, indicando cómo implementa dicho tipo las operaciones de la clase. Un tipo se puede declarar como instancia de varias clases usando deriving en la definición del tipo. Las clases pueden extenderse mediante el propio mecanismo class.

Cuando los tipos son genéricos, es posible que necesitemos imponer contextos (pertenencia a clases) a sus argumentos.

Modelo Operacional

Un programa funcional consta de:

1. Ecuaciones de definición de función.
2. Expresión inicial (sin variables libres).

La ejecución de un programa funcional se realiza evaluando (encadenamiento de pasos de reducción) la expresión inicial asociada. El concepto de sustitución se utiliza para formalizar el paso de parámetros como emparejamiento (matching) entre la expresión a evaluar y la parte izquierda de la ecuación.

• Una sustitución x es una función de variables para un conjunto finito de variables.
• La aplicación de una sustitución a una expresión se denomina instanciación.

Redex y Formas Normales

Un redex es cualquier instancia de la parte izquierda de una ecuación. Las expresiones que no tienen redexes se denominan formas normales. La evaluación de una expresión consiste en aplicar sucesivos pasos de reducción hasta obtener una forma normal.

Según la estrategia de reducción escogida, el resultado puede cambiar. Hay dos modelos de evaluación principales: Impaciente (Eager) y Perezoso (Lazy).

Evaluación Perezosa

La evaluación perezosa solo evalúa los argumentos si es necesario para aplicar alguna de las ecuaciones. Esto puede llevar a la no terminación, pero permite operar con estructuras de datos infinitas.

Eficiencia de la Evaluación

La eficiencia de la evaluación depende del programa y de la estrategia de evaluación utilizada.

Tipos de Evaluación

• Con éxito: Termina y obtiene un valor.
• Con fallo: Termina pero no obtiene un valor.
• Incompleta: No termina.

Funciones Anónimas y Otros Conceptos

Funciones Anónimas

Haskell permite definir funciones anónimas (o funciones sin nombre) usando expresiones lambda (con la "\").

Composición de Funciones

La composición de funciones es un patrón de cómputo habitual. Si la solución a un problema consta de varias etapas, podemos abordar cada una como funciones independientes y componerlas todas para obtener la solución final.

Iteradores

Los iteradores permiten trabajar de forma eficiente en tiempo y memoria con tipos de datos iterables (por ejemplo, listas, secuencias).

Compresores

Los compresores (lo contrario de los iteradores) procesan elementos de una lista y devuelven un valor o expresión que se calcula aplicando un operador a los elementos.

MapReduce

El uso de map y fold ha inspirado un estilo muy eficiente de procesamiento de secuencias, que tiene un gran impacto en el procesamiento de datos a gran escala (acceso y recuperación de información, cloud computing, etc.).

Programar sistemas distribuidos es difícil. Si utilizamos el sistema MapReduce, el sistema distribuye la carga. El esquema MapReduce resulta ser una abstracción muy útil que simplifica y optimiza la computación a gran escala. MapReduce ha inspirado a otros lenguajes como C++, Java, etc.