En informática , las flechas o pernos son una clase de tipo utilizada en programación para describir cálculos de forma pura y declarativa . Propuestas por primera vez por el científico informático John Hughes como una generalización de las mónadas , las flechas proporcionan una forma referencialmente transparente de expresar relaciones entre los pasos lógicos de un cálculo. [1] A diferencia de las mónadas, las flechas no limitan los pasos a tener una y solo una entrada. Como resultado, se han utilizado en programación reactiva funcional , programación sin puntos y analizadores sintácticos , entre otras aplicaciones. [1] [2]
Aunque las flechas ya se utilizaban antes de que se las reconociera como una clase distinta, no fue hasta el año 2000 que John Hughes publicó por primera vez una investigación centrada en ellas. Hasta entonces, las mónadas habían demostrado ser suficientes para la mayoría de los problemas que requerían la combinación de lógica de programa en código puro. Sin embargo, algunas bibliotecas útiles , como la biblioteca Fudgets para interfaces gráficas de usuario y ciertos analizadores eficientes, desafiaban la reescritura en forma monádica. [1]
El concepto formal de flechas se desarrolló para explicar estas excepciones al código monádico y, en el proceso, las mónadas mismas resultaron ser un subconjunto de las flechas. [1] Desde entonces, las flechas han sido un área activa de investigación. Sus leyes y operaciones subyacentes se han refinado varias veces, y formulaciones recientes como el cálculo de flechas requieren solo cinco leyes. [3]
En la teoría de categorías , las categorías de Kleisli de todas las mónadas forman un subconjunto propio de las flechas de Hughes. [1] Si bien durante un tiempo se creyó que las categorías de Freyd eran equivalentes a las flechas, [4] desde entonces se ha demostrado que las flechas son incluso más generales. De hecho, las flechas no son simplemente equivalentes, sino directamente iguales a las categorías de Freyd enriquecidas . [5]
Al igual que todas las clases de tipos, las flechas pueden considerarse como un conjunto de cualidades que se pueden aplicar a cualquier tipo de datos . En el lenguaje de programación Haskell , las flechas permiten que las funciones (representadas en Haskell por ->símbolos) se combinen en una forma reificada . Sin embargo, el término real "flecha" también puede provenir del hecho de que algunas flechas (pero no todas) corresponden a los morfismos (también conocidos como "flechas" en la teoría de categorías) de diferentes categorías de Kleisli. Como es un concepto relativamente nuevo, no existe una única definición estándar, pero todas las formulaciones son lógicamente equivalentes, presentan algunos métodos requeridos y obedecen estrictamente ciertas leyes matemáticas. [6]
La descripción que utilizan actualmente las bibliotecas estándar de Haskell requiere solo tres operaciones básicas:
arr : ( s -> t ) -> A s t primero : A s t -> A ( s , u ) ( t , u ) ( >>> ) : A s t -> A t u -> A s u Aunque solo estos tres procedimientos son estrictamente necesarios para definir una flecha, se pueden derivar otros métodos para que sea más fácil trabajar con flechas en la práctica y la teoría.
Se puede derivar otro método útil a partir de arr y first (y de donde se puede derivar first ):
( *** ) : A s t -> A u v -> A ( s , u ) ( t , v ) Además de tener algunos procedimientos bien definidos, las flechas deben obedecer ciertas reglas para cualquier tipo al que se puedan aplicar:
arr id == id arr ( f >>> g ) == arr f >>> arr g primero ( f >>> g ) == primero f >>> primero g arr ( primera f ) == primera ( arr f ) Las leyes restantes restringen el comportamiento del método de canalización cuando se invierte el orden de una composición, lo que también permite simplificar expresiones :
arr ( id *** g ) >>> primera f == primera f >>> arr ( id *** g ) primera f >>> arr (( s , t ) -> s ) == arr (( s , t ) -> s ) >>> f primero ( primera f ) >>> arr ( (( s , t ), u ) -> ( s ,( t , u )) ) == arr ( (( s , t ), u ) -> ( s ,( t , u )) ) >>> primera f Las flechas se pueden ampliar para adaptarse a situaciones específicas definiendo operaciones y restricciones adicionales. Las versiones más utilizadas incluyen flechas con opción, que permiten que un cálculo tome decisiones condicionales , y flechas con retroalimentación , que permiten que un paso tome sus propias salidas como entradas. Otro conjunto de flechas, conocidas como flechas con aplicación, rara vez se utilizan en la práctica porque en realidad son equivalentes a las mónadas. [6]
Las flechas tienen varios beneficios, principalmente derivados de su capacidad de hacer que la lógica del programa sea explícita pero concisa. Además de evitar los efectos secundarios , la programación puramente funcional crea más oportunidades para el análisis de código estático . Esto, a su vez, puede conducir teóricamente a mejores optimizaciones del compilador , una depuración más sencilla y características como el azúcar sintáctico . [6]
Aunque ningún programa requiere estrictamente flechas, éstas generalizan gran parte del paso de funciones denso que requeriría de otro modo el código declarativo puro. También pueden fomentar la reutilización del código al otorgar a los vínculos comunes entre los pasos del programa sus propias definiciones de clase. La capacidad de aplicar a los tipos de forma genérica también contribuye a la reutilización y mantiene las interfaces simples. [6]
Las flechas tienen algunas desventajas, incluido el esfuerzo inicial de definir una flecha que satisfaga las leyes de flechas. Debido a que las mónadas suelen ser más fáciles de implementar y las características adicionales de las flechas pueden ser innecesarias, a menudo es preferible utilizar una mónada. [6] Otro problema, que se aplica a muchas construcciones de programación funcional , es la compilación eficiente del código con flechas en el estilo imperativo utilizado por los conjuntos de instrucciones de las computadoras . [ cita requerida ]
Debido al requisito de tener que definir una arrfunción para levantar funciones puras, la aplicabilidad de las flechas es limitada. Por ejemplo, las transformaciones bidireccionales no pueden ser flechas, porque uno necesitaría proporcionar no solo una función pura, sino también su inversa, cuando se usa arr. [8] Esto también limita el uso de flechas para describir marcos reactivos basados en push que detienen la propagación innecesaria. De manera similar, el uso de pares para tuplar valores juntos da como resultado un estilo de codificación difícil que requiere combinadores adicionales para reagrupar valores y plantea preguntas fundamentales sobre la equivalencia de flechas agrupadas de diferentes maneras. Estas limitaciones siguen siendo un problema abierto, y extensiones como Flechas generalizadas [8] y FRP N-ario [9] exploran estos problemas.
Gran parte de la utilidad de las flechas se encuentra en clases más generales como Profunctor (que solo requiere precomposición y poscomposición con funciones), que tienen aplicación en óptica. Una flecha es esencialmente un profunctor fuerte que también es una categoría, aunque las leyes son ligeramente diferentes.
