quel est le but des flèches?

63

J'apprends la programmation fonctionnelle avec Haskell et j'essaie de saisir des concepts en commençant par comprendre pourquoi j'en ai besoin.

J'aimerais connaître l'objectif des flèches dans les langages de programmation fonctionnels. Quel problème résolvent-ils? J'ai vérifié http://en.wikibooks.org/wiki/Haskell/Understanding_arrows et http://www.cse.chalmers.se/~rjmh/afp-arrows.pdf . Tout ce que je comprends, c’est qu’ils servent à décrire des graphiques pour les calculs et qu’ils permettent un codage plus aisé du style sans point.

L'article suppose que le style sans points est généralement plus facile à comprendre et à écrire. Cela me semble assez subjectif. Dans un autre article ( http://en.wikibooks.org/wiki/Haskell/StephensArrowTutorial#Hangman:_Main_program ), un jeu du pendu est implémenté, mais je ne vois pas comment les flèches rendent cette implémentation naturelle.

Je pourrais trouver beaucoup d'articles décrivant le concept, mais rien sur la motivation.

Qu'est-ce qui me manque?

Simon Bergot
la source

Réponses:

43

Je me rends compte que j'arrive en retard à la fête, mais vous avez eu deux réponses théoriques et je voulais proposer une alternative pratique à la mastication. J'y viens en tant que membre de la famille Haskell, qui a néanmoins récemment exploré de force le sujet de Arrows pour un projet sur lequel je travaille actuellement.

Tout d'abord, vous pouvez résoudre de manière productive la plupart des problèmes dans Haskell sans atteindre les flèches. Certains Haskellers notables n'aiment vraiment pas et ne les utilisent pas (voir ici , ici et ici pour plus d'informations à ce sujet). Donc, si vous vous dites "Hé, je n'ai pas besoin de ça", comprenez que vous pouvez vraiment avoir raison.

Ce que j’ai trouvé le plus frustrant à propos des Arrows lorsque je les ai appris pour la première fois, c’est la façon dont les tutoriels sur le sujet ont inévitablement abouti à l’analogie des circuits. Si vous regardez le code Arrow - la variété sucrée, au moins - cela ne ressemble en rien à une langue de définition matérielle. Vos entrées sont alignées à droite et vos sorties à gauche, et si vous ne les connectez pas correctement, elles ne peuvent tout simplement pas être déclenchées. Je me suis dit: vraiment? Est-ce là que nous avons fini? Avons-nous créé un langage tellement haut niveau qu'il se compose à nouveau de fils de cuivre et de soudure?

La bonne réponse à cette question, autant que j'ai pu le déterminer, est: en fait, oui. Le cas d'utilisation qui tue actuellement pour Arrows est le PRF (pensez à Yampa, aux jeux, à la musique et aux systèmes réactifs en général). Le problème auquel FRP est confronté est en grande partie le même que tous les autres systèmes de messagerie synchrone: comment brancher un flux continu d'entrées dans un flux continu de sorties sans laisser tomber les informations pertinentes ou provoquer des fuites. Vous pouvez modéliser les flux sous forme de listes (plusieurs systèmes FRP récents utilisent cette approche), mais lorsque vous avez beaucoup de listes d’entrées, il est presque impossible de les gérer. Vous devez vous isoler du courant.

Ce que les flèches permettent dans les systèmes FRP, c’est la composition de fonctions dans un réseau tout en faisant totalement abstraction de toute référence aux valeurs sous-jacentes transmises par ces fonctions. Si vous débutez dans la FP, cela peut être déroutant au début, puis époustouflant lorsque vous en avez absorbé les implications. Vous n’avez que récemment assimilé l’idée que les fonctions peuvent être abstraites et comment comprendre une liste comme [(*), (+), (-)]étant de type [(a -> a -> a)]. Avec les flèches, vous pouvez pousser l’abstraction d’un calque plus loin.

Cette capacité additionnelle d'abstraction comporte ses propres dangers. D'une part, cela peut pousser GHC dans des situations critiques où il ne sait pas quoi faire de vos hypothèses de type. Vous devrez être prêt à penser au niveau des caractères - c’est une excellente occasion d’en apprendre davantage sur les genres, les RankNTypes et d’autres sujets de ce type.

Il existe également un certain nombre d'exemples de ce que j'appellerais "Stupid Arrow Stunts", où le codeur cherche un combinateur de Arrow simplement parce qu'il ou elle veut montrer un tour astucieux avec des n-uplets. (Voici ma propre contribution triviale à la folie .) Sentez-vous libre d'ignorer un tel hot dogging lorsque vous le rencontrez à l'état sauvage.

NOTE: Comme je l'ai mentionné ci-dessus, je suis un noob relatif. Si j'ai promulgué les idées fausses ci-dessus, n'hésitez pas à me corriger.

personne
la source
2
Je suis heureux de n'avoir encore rien accepté. Merci d'avoir fourni cette réponse. Il est plus axé sur les utilisateurs. Les exemples sont super. Les parties subjectives sont clairement définies et équilibrées. J'espère que les personnes qui ont voté contre cette question reviendront et verront cela.
Simon Bergot
Bien que les flèches soient définitivement le mauvais outil pour votre solution liée, j’ai besoin de mentionner qu’il removeAt' n = arr(\ xs -> (xs,xs)) >>> arr (take (n-1)) *** arr (drop n) >>> arr (uncurry (++)) >>> returnApeut être écrit de manière plus concise et claire removeAt' n = (arr (take $ n-1) &&& arr (drop n)) >>> (arr $ uncurry (++)).
cemper93
30

C'est en quelque sorte une réponse "douce", et je ne suis pas sûr si une référence l'indique réellement de cette manière, mais c'est comme cela que je viens de penser aux flèches:

Un type de flèche A b cest fondamentalement une fonction b -> cmais avec plus de structure de la même manière qu'une valeur monadique M aa plus de structure qu'un ancien a.

Maintenant, la nature de cette structure supplémentaire dépend de l'instance de flèche particulière dont vous parlez. Tout comme avec les monades IO aet Maybe achacun a une structure supplémentaire différente.

La chose que vous obtenez avec les monades est une incapacité à aller d'un an M aà l'autre a. Cela peut sembler être une limitation, mais il s’agit en réalité d’une fonctionnalité: le système de types vous empêche de transformer une valeur monadique en une ancienne valeur. Vous ne pouvez utiliser cette valeur qu'en participant à la monade via >>=ou aux opérations primitives de l'instance de monad particulière.

De même, vous obtenez A b cune incapacité à créer une nouvelle "fonction" produisant du b-consommateur. La flèche vous protège de la consommation bet de la création d'une cexception en participant aux divers combinateurs de flèche ou en utilisant les opérations primitives de l'instance de flèche particulière.

Par exemple, les fonctions de signal dans Yampa sont approximativement (Time -> a) -> (Time -> b), mais en plus, elles doivent obéir à une certaine restriction de causalité : la sortie à la fois test déterminée par les valeurs passées du signal d'entrée: vous ne pouvez pas regarder dans le futur. Au lieu de programmer avec (Time -> a) -> (Time -> b), vous programmez avec SF a bet vous construisez vos fonctions de signal à partir de primitives. Il se trouve que depuis, il SF a bse comporte beaucoup comme une fonction, de sorte que la structure commune s'appelle une "flèche".

Lambdageek
la source
"La flèche vous protège de la consommation bet de la création d'une cexception en participant aux divers combinateurs de flèche ou en utilisant les opérations primitives de l'instance de flèche particulière." Avec des excuses pour avoir répondu à cette réponse ancienne: cette phrase m'a fait penser à des types linéaires, c'est-à-dire que les ressources ne peuvent pas être clonées ni disparues. Pensez-vous qu'il pourrait y avoir un lien?
Glaebhoerl
14

J'aime penser que les flèches, comme les monades et les foncteurs, permettent au programmeur de créer des compositions de fonctions exotiques.

Sans monades ni flèches (ni foncteurs), la composition de fonctions dans un langage fonctionnel est limitée à l'application d'une fonction au résultat d'une autre fonction. Avec les monades et les foncteurs, vous pouvez définir deux fonctions, puis écrire un code réutilisable séparé qui spécifie comment ces fonctions, dans le contexte de la monade particulière, interagissent les unes avec les autres et avec les données qui y sont transmises. Ce code est placé dans le code de liaison de la Monad. Ainsi, une monade est une vue unique, juste un conteneur pour un code de liaison réutilisable. Les fonctions se composent différemment dans le contexte d'une monade d'une autre monade.

Un exemple simple est la monade Maybe, où la fonction bind contient du code tel que si une fonction A est composée d'une fonction B dans une monade Maybe et que B produit un Nothing, le code de liaison assurera que la composition du deux fonctions produisent un Nothing, sans prendre la peine d'appliquer A à la valeur Nothing qui sort de B. S'il n'y avait pas de monade, le programmeur devrait écrire du code dans A pour tester une entrée Nothing.

Monads signifie également que le programmeur n'a pas besoin de saisir explicitement les paramètres requis par chaque fonction dans le code source - la fonction bind gère le passage des paramètres. Donc, en utilisant des monades, le code source peut commencer à ressembler davantage à une chaîne statique de noms de fonctions, plutôt que de ressembler à la fonction A "appelle" la fonction B avec les paramètres C et D - le code commence à ressembler davantage à un circuit électronique qu'à un circuit électronique. machine en mouvement - plus fonctionnelle que l'impératif.

Les flèches connectent également des fonctions avec une fonction de liaison, fournissant des fonctionnalités réutilisables et masquant des paramètres. Mais les flèches peuvent elles-mêmes être connectées et composées, et peuvent éventuellement acheminer des données vers d'autres flèches lors de l'exécution. Maintenant, vous pouvez appliquer des données à deux chemins de flèches, qui "font des choses différentes" pour les données et réassembler le résultat. Vous pouvez également sélectionner la branche des flèches vers laquelle transmettre les données, en fonction de la valeur des données. Le code qui en résulte ressemble encore plus à un circuit électronique, avec des commutateurs, des retards, une intégration, etc. Le programme semble très statique et vous ne devriez pas être en mesure de voir beaucoup de manipulations de données. Il y a de moins en moins de paramètres à prendre en compte, et moins besoin de penser aux valeurs que les paramètres peuvent prendre ou non.

Écrire un programme Arrowized implique principalement de sélectionner des flèches standard telles que des séparateurs, des commutateurs, des retards et des intégrateurs, de lever des fonctions dans ces flèches et de relier les flèches ensemble pour former des flèches plus grosses. Dans la programmation réactive fonctionnelle fléchée, les flèches forment une boucle, les entrées du monde étant combinées aux sorties de la dernière itération du programme, de sorte que les sorties réagissent aux entrées du monde réel.

Le temps est l'une des valeurs du monde réel. Dans Yampa, la flèche de fonction de signal insère de manière invisible le paramètre de temps dans le programme. Vous n’accédez jamais à la valeur de temps, mais si vous connectez une flèche d’intégrateur au programme, elle affichera des valeurs intégrées au fil du temps que vous pourrez ensuite utiliser pour passer à. autres flèches.

Robert Onslow
la source
mais cela ressemble à un foncteur applicatif (un wrapper autour d’une fonction, qui fournit des fonctions d’aide, dans un contexte spécifique, pour la réutilisation de fonctions déjà existantes pour les types wrapped). J'ai certainement besoin d'en lire plus pour comprendre, mais vous pouvez peut-être aider en signalant ce qui me manque
Belun
3

Juste un ajout aux autres réponses: Personnellement, cela m’aide beaucoup de comprendre ce qu’est un tel concept (mathématiquement) et son rapport avec d’autres concepts que je connais.

Dans le cas des flèches, le texte suivant a été utile: il compare les monades, les foncteurs applicatifs (idiomes) et les flèches: les idiomes sont inconscients, les flèches sont méticuleuses, les monades sont promiscuilles de Sam Lindley, Philip Wadler et Jeremy Yallop.

De plus, je pense que personne n’a mentionné ce lien qui pourrait vous fournir des idées et de la littérature sur le sujet.

Petr Pudlák
la source