Qu'est-ce qu'une flèche et comment l'utiliser ?

Question

J'ai essayé d'apprendre la signification de flèches mais je ne les comprenais pas.

J'ai utilisé le tutoriel de Wikibooks. Je pense que le problème de Wikibooks est principalement qu'il semble être écrit pour quelqu'un qui comprend déjà le sujet.

Quelqu'un peut-il m'expliquer ce que sont les flèches et comment je peux les utiliser ?

Answer 1

Je ne sais pas un tutoriel, mais je pense que c'est plus facile à comprendre flèches si vous regardez certains des exemples concrets. Le plus gros problème que j'ai eu à apprendre comment utiliser les flèches était qu'aucun des tutoriels ou des exemples montrent comment utiliser les flèches, juste la façon de composer. Donc, avec cela à l'esprit, voici mon mini-tutoriel. Je vais examiner les deux flèches: les fonctions et définies par l'utilisateur type de flèche MyArr.

-- type representing a computation
data MyArr b c = MyArr (b -> (c,MyArr b c))

1) Une Flèche est un calcul à partir d'une entrée d'un type spécifié à la sortie d'un type spécifié. La flèche typeclass prend trois arguments de type: le type de flèche, le type d'entrée, et le type de sortie. En regardant l'exemple de la tête de flèche instances, nous trouvons:

instance Arrow (->) b c where
instance Arrow MyArr b c where

La Flèche (soit (->) ou MyArr) est une abstraction d'un calcul.

Pour une fonction b -> c, b à l'entrée et c à la sortie.
Pour un MyArr b c, b à l'entrée et c à la sortie.

2) Pour exécuter une flèche de calcul, vous utilisez une fonction spécifique à votre type de flèche. Pour les fonctions en vous il suffit d'appliquer la fonction à un argument. Pour d'autres flèches, il doit y avoir une fonction distincte (comme runIdentity, runState, etc. pour monades).

-- run a function arrow
runF :: (b -> c) -> b -> c
runF = id

-- run a MyArr arrow, discarding the remaining computation
runMyArr :: MyArr b c -> b -> c
runMyArr (MyArr step) = fst . step

3) Flèches sont fréquemment utilisés pour traiter une liste d'entrées. Pour les fonctions, ils peuvent être réalisés en parallèle, mais pour certains flèches de sortie à une étape donnée dépend précédente entrées (par exemple, en gardant un total des entrées).

-- run a function arrow over multiple inputs
runFList :: (b -> c) -> [b] -> [c]
runFList f = map f

-- run a MyArr over multiple inputs.
-- Each step of the computation gives the next step to use
runMyArrList :: MyArr b c -> [b] -> [c]
runMyArrList _ [] = []
runMyArrList (MyArr step) (b:bs) = let (this, step') = step b
                                   in this : runMyArrList step' bs

C'est une des raisons les Flèches sont utiles. Ils fournissent un modèle de calcul qui peut implicitement faire usage d'état sans jamais exposer cet état pour le programmeur. Le programmeur peut utiliser arrowized de calculs et de les combiner pour créer des systèmes complexes.

Voici un MyArr qui tient compte du nombre d'entrées qu'il a reçu:

-- count the number of inputs received:
count :: MyArr b Int
count = count' 0
  where
    count' n = MyArr (\_ -> (n+1, count' (n+1)))

Maintenant la fonction runMyArrList count prendra une liste de longueur n en entrée et retourne une liste d'Entiers de 1 à n.

Notez que nous n'avons pas encore utilisé tout "flèche", qui est l'une des Flèches de la classe de méthodes ou de fonctions écrites en termes d'entre eux.

4) la Plupart du code ci-dessus est spécifique à chaque Flèche exemple[1]. Tout en Control.Arrow (et Control.Category) est sur la composition des flèches pour faire de nouvelles flèches. Si nous prétendons que la Catégorie est la partie de la Flèche à la place d'une autre classe:

-- combine two arrows in sequence
>>> :: Arrow a => a b c -> a c d -> a b d

-- the function arrow instance
-- >>> :: (b -> c) -> (c -> d) -> (b -> d)
-- this is just flip (.)

-- MyArr instance
-- >>> :: MyArr b c -> MyArr c d -> MyArr b d

L' >>> fonction prend deux flèches et utilise la sortie de la première comme entrée pour la seconde.

Voici un autre opérateur, communément appelée "distribution":

-- &&& applies two arrows to a single input in parallel
&&& :: Arrow a => a b c -> a b c' -> a b (c,c')

-- function instance type
-- &&& :: (b -> c) -> (b -> c') -> (b -> (c,c'))

-- MyArr instance type
-- &&& :: MyArr b c -> MyArr b c' -> MyArr b (c,c')

-- first and second omitted for brevity, see the accepted answer from KennyTM's link
-- for further details.

Depuis Control.Arrow fournit un moyen de combiner les calculs, voici un exemple:

-- function that, given an input n, returns "n+1" and "n*2"
calc1 :: Int -> (Int,Int)
calc1 = (+1) &&& (*2)

J'ai souvent trouvé des fonctions comme calc1 utile dans les plis, ou de fonctions qui opèrent sur des pointeurs par exemple.

L' Monad type de classe nous donne un moyen de combiner monadique les calculs en un seul nouveau monadique de calcul à l'aide de l' >>= fonction. De même, l' Arrow classe nous donne les moyens de combiner arrowized les calculs en un seul nouveau arrowized calcul à l'aide de quelques fonctions primitives (first, arr, et ***, avec >>> et id de Contrôle.La catégorie). Également semblable à Monades, la question de "Ce qui fait une flèche de faire?" ne peut pas être généralement répondu. Il dépend de la flèche.

Malheureusement, je ne connais de nombreux exemples de flèche instances dans la nature. Fonctions et PRF semblent être les applications les plus courantes. HXT est la seule autre significatif de l'utilisation qui vient à l'esprit.

[1] à l'Exception de count. Il est possible d'écrire une fonction de comptage qui fait la même chose pour n'importe quelle instance d' ArrowLoop.

Answer 2

D'après votre historique sur Stack Overflow, je vais supposer que vous êtes à l'aise avec certaines des autres classes de type standard, en particulier Functor y Monoid et de commencer par une brève analogie à partir de ceux-ci.

L'opération unique sur Functor es fmap qui sert de version généralisée de map sur des listes. C'est à peu près la raison d'être de la classe de type : elle définit des "choses sur lesquelles on peut mapper". Ainsi, dans un sens Functor représente une généralisation de cet aspect particulier des listes.

Les opérations de Monoid sont des versions généralisées de la liste vide et (++) Il définit les "choses qui peuvent être combinées de manière associative, avec une chose particulière qui est une valeur d'identité". Les listes sont à peu près la chose la plus simple qui corresponde à cette description. Monoid représente une généralisation de cet aspect des listes.

De la même manière que les deux précédentes, les opérations sur les Category sont des versions généralisées de id y (.) et il définit "les choses qui relient deux types dans une direction particulière et qui peuvent être connectées tête-bêche". Il s'agit donc d'une généralisation de cet aspect de la notion de fonctions . Cette généralisation n'englobe pas les notions de curage et d'application de la fonction.

En Arrow s'appuie sur la classe de type Category mais le concept sous-jacent est le même : Arrow sont des éléments qui se composent comme des fonctions et ont une "flèche d'identité" définie pour tout type. Les opérations supplémentaires définies sur les Arrow elle-même ne fait que définir un moyen d'élever une fonction arbitraire au rang de Arrow et un moyen de combiner deux flèches "en parallèle" en une seule flèche entre les tuples.

La première chose à garder à l'esprit est donc que bâtiment des expressions Arrow sont essentiellement des compositions élaborées de fonctions . Les combinateurs tels que (***) y (>>>) sont destinés à l'écriture en style "sans point", tandis que proc permet d'attribuer des noms temporaires aux entrées et aux sorties lors du câblage.

Il est utile de noter ici que, même si les Arrow sont parfois décrits comme étant "l'étape suivante" par rapport aux Monad il n'y a pas vraiment de relation significative entre les deux. Pour tout Monad vous pouvez travailler avec des flèches de Kleisli, qui sont simplement des fonctions avec un type comme a -> m b . Les (<=<) opérateur en Control.Monad est une composition fléchée pour ces derniers. D'autre part, Arrow ne vous permettent pas d'obtenir un Monad à moins que vous n'incluiez également l'option ArrowApply classe. Il n'y a donc pas de lien direct en tant que tel.

La différence essentielle réside dans le fait que, alors que les Monad peuvent être utilisées pour séquencer les calculs et faire les choses étape par étape, Arrow sont en quelque sorte "intemporelles", tout comme les fonctions ordinaires. Elles peuvent inclure des mécanismes et des fonctionnalités supplémentaires qui sont ajoutés par les (.) mais il s'agit plutôt de construire un pipeline, et non d'accumuler des actions.

Les autres classes de type apparentées ajoutent des fonctionnalités supplémentaires à une flèche, comme la possibilité de combiner des flèches avec des Either ainsi que (,) .

---

Mon exemple préféré d'une Arrow es transducteurs de flux avec état qui se présentent de la manière suivante :

data StreamTrans a b = StreamTrans (a -> (b, StreamTrans a b))

A StreamTrans convertit une valeur d'entrée en une sortie et une version "mise à jour" d'elle-même. Monad .

Rédaction d'instances pour Arrow et ses classes de type connexes pour le type ci-dessus peut être un bon exercice pour comprendre comment ils fonctionnent !

J'ai également rédigé un réponse similaire précédemment qui peuvent vous être utiles.

Answer 3

J'aimerais ajouter que les flèches en Haskell sont bien plus simples qu'il n'y paraît en se basant sur la littérature. Il s'agit simplement d'abstractions de fonctions.

Pour voir comment cela est utile en pratique, considérez que vous avez un tas de fonctions fonctions que vous voulez composer, dont certaines sont pures et d'autres sont monadiques. Par exemple, f :: a -> b , g :: b -> m1 c et h :: c -> m2 d .

En connaissant chacun des types impliqués, je pourrais construire une composition à la main, mais le type de sortie de la composition devrait refléter les types de monades intermédiaires intermédiaires (dans le cas ci-dessus, m1 (m2 d) ). Et si je voulais simplement traiter les fonctions comme s'il s'agissait simplement de a -> b , b -> c et c -> d ? C'est-à-dire, je veux faire abstraction de la présence des monades et ne raisonner que sur les types sous-jacents. Je peux utiliser les flèches pour faire exactement cela.

Voici une flèche qui fait abstraction de la présence de l'IO pour les fonctions dans l'environnement IO, de sorte que je puisse les composer avec des fonctions pures sans le sans que le code de composition n'ait besoin de savoir que l'IO est impliqué . Nous commençons par définir un IOArrow pour envelopper les fonctions IO :

data IOArrow a b = IOArrow { runIOArrow :: a -> IO b }

instance Category IOArrow where
  id = IOArrow return
  IOArrow f . IOArrow g = IOArrow $ f <=< g

instance Arrow IOArrow where
  arr f = IOArrow $ return . f
  first (IOArrow f) = IOArrow $ \(a, c) -> do
    x <- f a
    return (x, c)

Je crée ensuite quelques fonctions simples que je souhaite composer :

foo :: Int -> String
foo = show

bar :: String -> IO Int
bar = return . read

Et utilisez-les :

main :: IO ()
main = do
  let f = arr (++ "!") . arr foo . IOArrow bar . arr id
  result <- runIOArrow f "123"
  putStrLn result

Ici, j'appelle IOArrow et runIOArrow, mais si je transmettais ces flèches dans une bibliothèque de fonctions polymorphes, elles n'auraient besoin que d'accepter arguments de type "Flèche a => a b c". Aucun code de la bibliothèque n'aurait besoin d'être de la bibliothèque n'aurait besoin d'être informé de l'existence d'une monade. Seuls le créateur et l'utilisateur final de la a besoin de le savoir.

La généralisation de la flèche IO pour les fonctions dans n'importe quelle monade est appelée "flèche de Kleisli". et il existe déjà une flèche intégrée pour cela :

main :: IO ()
main = do
  let g = arr (++ "!") . arr foo . Kleisli bar . arr id
  result <- runKleisli g "123"
  putStrLn result

Vous pouvez bien entendu utiliser les opérateurs de composition de flèches et la syntaxe proc pour pour rendre un peu plus clair le fait que des flèches sont impliquées :

arrowUser :: Arrow a => a String String -> a String String
arrowUser f = proc x -> do
  y <- f -< x
  returnA -< y

main :: IO ()
main = do
  let h =     arr (++ "!")
          <<< arr foo
          <<< Kleisli bar
          <<< arr id
  result <- runKleisli (arrowUser h) "123"
  putStrLn result

Il convient ici de préciser que, même si main sait que la monade IO est impliquée, arrowUser ne le fait pas. Il n'y aurait aucun moyen de "cacher" l'OI à l'administration centrale de l'UE. arrowUser sans flèches -- pas sans recourir à des unsafePerformIO pour faire tourner le monadique intermédiaire en une valeur pure (et donc de perdre ce contexte pour toujours). pour toujours). Par exemple :

arrowUser' :: (String -> String) -> String -> String
arrowUser' f x = f x

main' :: IO ()
main' = do
  let h      = (++ "!") . foo . unsafePerformIO . bar . id
      result = arrowUser' h "123"
  putStrLn result

Essayez d'écrire cela sans unsafePerformIO et sans arrowUser' devant de traiter les arguments de type Monad.

Answer 4

Il y a les notes de conférence de John Hughes d'un atelier AFP (Advanced Functional Programming). Notez qu'elles ont été écrites avant que les classes Arrow ne soient modifiées dans les bibliothèques Base :

http://www.cse.chalmers.se/~rjmh/afp-arrows.pdf

Answer 5

Lorsque j'ai commencé à explorer les compositions d'Arrow (essentiellement les monades), mon approche était de me détacher de la syntaxe fonctionnelle et de la composition qui lui est le plus souvent associée et de commencer à comprendre ses principes à l'aide d'une approche plus déclarative. Dans cette optique, je trouve la décomposition suivante plus intuitive :

function(x) {
  func1result = func1(x)
  if(func1result == null) {
    return null
  } else {
    func2result = func2(func1result)
    if(func2result == null) {
      return null
    } else {
      func3(func2result)
    } 

Ainsi, en substance, pour une certaine valeur x Nous appelons d'abord une fonction dont nous supposons qu'elle peut renvoyer les données suivantes null (func1), un autre qui peut revenir en arrière. null ou être affecté à null de manière interchangeable, enfin, une troisième fonction qui peut également renvoyer null . Maintenant, étant donné la valeur x , passer x à func3, et seulement ensuite, s'il ne retourne pas null , passer cette valeur dans func2, et seulement si cette valeur n'est pas nulle, passer cette valeur dans func1. C'est plus déterministe et le flux de contrôle vous permet de construire une gestion des exceptions plus sophistiquée.

Ici, nous pouvons utiliser la composition de la flèche : (func3 <=< func2 <=< func1) x .