La classe de types Arrow, en Haskell

Voir aussi : video youtube - code source

Le concept de Monade est très classique en Haskell, et commence à se diffuser dans d’autres langage de programmation. Il existe également le concept d’Arrow, plus puissant, qui permet des applications oú les monades sont insuffisantes.

Cet article présente le concept d’Arrow et son utilisation, notamment via quelques exemples basiques. Il sera suivi de deux autres articles, présentant un type d’Arrow plus intéressant (le type Circuit) puis son utilisation pour programmer des interfaces utilisateur dans le style de la Programmation Fonctionnelle Réactive.

Généralités

Le concept d’Arrow

Historiquement, le concept d’Arrow est apparu en Haskell suite à un problème très concret. Deux chercheurs (Swierstra et Duponcheel) ont imaginé des combinateurs de parseurs optimisés mais leur idée n’était pas implémentable avec des monades (contrairement aux combinateurs de parseurs classiques). Ils ont alors utilisé le concept d’Arrow, issu de la théorie des catégories, pour implémenter leur idée. Par la suite, il s’est avéré que ce concept était intéressant pour bien d’autres applications (flux de données, interfaces utilisateurs…).

Intuitivement, on peut voir une monade (Monad m => m c) comme un contexte implémentant un type d’actions particulier. Ceci permet de réaliser successivement des actions (de type m) et de retourner une valeur finale (de type c). Par exemple, la monade IO permet de réaliser des actions d’entrée ou de sortie (lire un fichier, afficher à l’écran…) et éventuellement de retourner une valeur. Dans le cas des parseurs monadiques, une action va typiquement consommer le flux d’entrée et retourner un élément de l’AST.

Une arrow (Arrow a => a b c) peut être vue comme une monade qui peut produire une valeur de sortie mais également prendre une valeur en entrée. Ceci permet donc de réaliser des actions (de type a), en prenant une valeur d’entrée (de type b) et en retournant une valeur de sortie (de type c). Ainsi, on va pouvoir chainer des arrows pour implémenter des flux complexes et dans un contexte bien défini. Dans le cas des parseurs optimisés, une action consomme le flux d’entrée et retourne un élément de l’AST mais peut également recevoir des informations en entrée pour optimiser son étape de parsing.

La classe de types Arrow

Tout d’abord, on définit la classe Category de la façon (simplifiée) suivante :

class Cat.Category a where
  id :: a b b
  (.) :: a c d -> a b c -> a b d

Grossièrement, une catégorie implémente les notions d’identité et de composition. On peut alors définir la classe Arrow :

class Cat.Category a => Arrow a where
  arr :: (b -> c) -> a b c
  first :: a b c -> a (b, d) (c, d)

La fonction arr construit une arrow à partir d’une fonction pure. Par exemple, si p est une fonction qui prend un b et retourne un c, on obtient une arrow de b vers c, ce que l’on peut schématiser de la façon suivante :

La fonction first permet de convertir une arrow à une entrée et une sortie en arrow à deux entrées et deux sorties, où la première entrée/sortie correspond à l’arrow initiale (et la seconde, à l’arrow identité) :

Quelques autres opérations

À partir de ces définition de base, on a également d’autres opérations intéressantes.

(>>>) :: Cat.Category a =>
  a b c -> a c d -> a b d

L’opérateur (>>>) permet de chainer deux arrows/catégories (il s’agit de l’opérateur de composition où on a changé l’ordre des paramètres) :

(>>^) :: Arrow a => 
  a b c -> (c -> d) -> a b d

L’opérateur (>>^) permet de chainer une arrow avec une fonction pure. Plus exactement, f >>^ p est équivalent à f >>> arr p :

(&&&) :: a b c -> a b c' -> a b (c, c')

L’opérateur (&&&) applique deux arrows sur une même entrée, fournissant ainsi deux sorties :

Il existe encore d’autres fonctionnalités sur les arrows, notamment des classes dérivées (ArrowChoice, ArrowZero…) ainsi qu’une extension de langage (Arrows) permettant une notation do similaire à celle utilisée pour les monades (voir les exemples, plus loin).

Exemple 1 : Func

Un exemple d’arrow qui vient naturellement à l’esprit est la notion de fonction. On a bien une entrée et une sortie, et le contexte est tout simplement l’évaluation de fonctions pures.

Définir et instancier le type Func

Soit le type Func b c suivant, correspondant à une fonction de b vers c :

newtype Func b c = Func { runFunc :: b -> c }

Pour utiliser ce type comme une arrow, il suffit d’instancier les classes Category et Arrow :

instance Cat.Category Func where

  id :: Func b b
  id = Func id

  (.) :: Func c d -> Func b c -> Func b d
  Func q . Func p = Func (q . p)
  -- ou: g . f = Func (runFunc g . runFunc f)


instance Arrow Func where

  arr :: (b -> c) -> Func b c
  arr = Func

  first :: Func b c -> Func (b, d) (c, d)
  first (Func p) = Func $ \(x, y) -> (p x, y)
  -- ou: first f = Func $ \(x, y) -> (runFunc f x, y)

Définir et exécuter des arrows

On peut ensuite définir des arrows de type Func, par exemple qui ajoute 1 ou multiplie par 2 :

fPlus1 :: Func Int Int
fPlus1 = arr (+1)

fMul2 :: Func Int Int
fMul2 = arr (*2)

et exécuter une arrow de type Func sur une entrée donnée :

ghci> runFunc fPlus1 41
42

Combiner des arrows

L’intérêt de la classe Arrow pour notre type Func est de pouvoir utiliser toutes les fonctionnalités correspondantes, par exemple la composition avec (>>>) :

fMyProc1 :: Func Int Int
fMyProc1 = fPlus1 >>> fMul2

ghci> runFunc fMyProc1 1
4

Autre exemple, plus complexe :

fMyProc2 :: Func Int Int
fMyProc2 = fPlus1 >>> fMul2 >>> (arr (*3) &&& arr id) >>^ uncurry (+)

ghci> runFunc fMyProc2 1
8

Notation do sur des arrows

Comme mentionné plus haut, on a une notation do pour les arrows, similaire à celle sur les monades, via une extension de langage. Ainsi, l’exemple précédent peut s’écrire, en notation do :

fMyProc3 :: Func Int Int
fMyProc3 = proc x -> do
  y <- fPlus1 -< x
  z <- fMul2 -< y
  u1 <- arr (*3) -< z
  returnA -< u1 + z

On notera que la syntaxe est légèrement différente de celle pour les monades. Il faut notamment gérer explicitement l’entrée de chaque action, avec l’opérateur (-<).

Exemple 2 : StreamFunc

Type

Un autre exemple classique d’arrow est la gestion de flux. Un StreamFunc de b vers c correspond à une fonction qui consomme une liste de b pour produire une liste de c :

newtype StreamFunc b c = StreamFunc { runStreamFunc :: [b] -> [c] }


instance Cat.Category StreamFunc where

  id :: StreamFunc b b
  id = StreamFunc id

  (.) :: StreamFunc c d -> StreamFunc b c -> StreamFunc b d
  StreamFunc q . StreamFunc p = StreamFunc (q . p)


instance Arrow StreamFunc where

  arr :: (b -> c) -> StreamFunc b c
  arr p = StreamFunc (map p)

  first :: StreamFunc b c -> StreamFunc (b, d) (c, d)
  first (StreamFunc p) = StreamFunc $ \b ->
    let (xs, ys) = unzip b
    in zip (p xs) ys

On notera que c’est l’instanciation de Arrow qui définit le contexte de flux.

Exemples d’utilisation

Pour définir des arrows de type StreamFunc, il suffit de définir comment on traite chaque élément du flux :

sfMul2 :: StreamFunc Int Int
sfMul2 = arr (*2)

sfC2I :: StreamFunc Char Int
sfC2I = arr digitToInt

sfMyProc1 :: StreamFunc Char Int
sfMyProc1 = sfC2I >>> sfMul2

L’arrow sfMul2 multiplie par 2 chaque entier du flux, sfC2I convertit chaque caractère du flux en un entier et sfMyProc1 convertit chaque caractère du flux en entier et le multiplie par 2.

ghci> runStreamFunc sfMyProc1 "123"
[2,4,6]

Autre exemple, où on fait le même traitement mais en retournant également l’entrée initiale :

sfMyProc2 :: StreamFunc Char (Int, Char)
sfMyProc2 = sfC2I &&& arr id >>> first sfMul2

ghci> runStreamFunc sfMyProc2 "123"
[(2,'1'),(4,'2'),(6,'3')]

Autre implémentation possible :

sfMyProc2' :: StreamFunc Char (Int, Char)
sfMyProc2' = arr (\x -> (x,x)) >>> first (sfC2I >>> sfMul2)

Exemple 3 : Kleisli

Type

Le concept d’Arrow étant plus général que celui de Monade, on peut implémenter un type d’arrows correspondant aux monades : il s’agit de l’arrow de Kleisli, également appelée morphisme de Kleisli.

newtype Kleisli m b c = Kleisli { runKleisli :: b -> m c }


instance Monad m => Cat.Category (Kleisli m) where

  id :: Monad m => Kleisli m b b
  id = Kleisli return

  (.) :: Monad m => Kleisli m c d -> Kleisli m b c -> Kleisli m b d
  Kleisli q . Kleisli p = Kleisli $ \b -> do
      c <- p b 
      d <- q c
      return d
  -- ou: Kleisli q . Kleisli p = Kleisli (\b -> p b >>= q)


instance Monad m => Arrow (Kleisli m) where

  arr :: Monad m => (b -> c) -> Kleisli m b c
  arr p = Kleisli (return . p)

  first :: Monad m => Kleisli m b c -> Kleisli m (b, d) (c, d)
  first (Kleisli p) = Kleisli $ \(b, d) -> do
      c <- p b 
      return (c, d)
  -- ou: first (Kleisli p) = Kleisli (\(b, d) -> p b >>= \c -> return (c, d))

Grossièrement, le type Kleisli correspond à l’opérateur (>>=) sur une monade m. Ce type existe déjà dans le module Control.Arrow.

Exemples d’utilisation avec IO

On peut ensuite définir des actions, par exemple d’entrées/sorties (IO). Avec les monades classiques, on écrirait quelque chose comme :

mProcIO1 :: IO Int
mProcIO1 = do
  putStrLn "hello"
  return 42

ghci> mRes1 <- mProcIO1
hello

ghci> mRes1
42

Avec l’arrow de Kleisli, on peut écrire  :

kProcIO1 :: Kleisli IO () Int
kProcIO1 = Kleisli $ \() -> do
  putStrLn "hello"
  return 42

ghci> kRes1 <- runKleisli kProcIO1 ()
hello

ghci> kRes1
42

On a donc un code très similaire entre la monade et l’arrow. La principale différence est que l’arrow permet également d’entrer des données :

kProcIO1 :: Kleisli IO (Int, Int) Int
kProcIO1 = Kleisli $ \(x, y) -> do
  print x
  print y
  return (x+y)

ghci> kRes2 <- runKleisli kProcIO2 (20, 22)
20
22

ghci> kRes2
42

Exemples d’utilisation avec Maybe

Autre exemple, avec la monade Maybe où on définit et compose des arrows :

kMul2 :: Kleisli Maybe Double Double
kMul2 = arr (*2)

kSqrt :: Kleisli Maybe Double Double
kSqrt = Kleisli (\x -> if x >= 0 then Just (sqrt x) else Nothing)

kProcMaybe1 :: Kleisli Maybe Double Double
kProcMaybe1 = kSqrt >>> kMul2

ghci> runKleisli kProcMaybe1 4
Just 4.0

ghci> runKleisli kProcMaybe1 (-4) 
Nothing

Ou encore avec la notation do des arrows :

kProcMaybe2 :: Kleisli Maybe Double Double
kProcMaybe2 = proc x0 -> do
  x1 <- kSqrt -< x0
  kMul2 -< x1

ghci> runKleisli kProcMaybe2 4 
Just 4.0

ghci> runKleisli kProcMaybe2 (-4)
Nothing

Conclusion

Le concept d’Arrow est plus général que le concept de monade. Il s’agit d’un contexte pouvant produire une valeur mais également de prendre des entrées. Ainsi, on peut définir des séquences d’actions simples, comme celles présentées ici, mais également plus complexes, comme celles présentées dans le prochain article avec le type Circuit.

Voir également :

• Haskell wiki: Arrow
• Haskell wiki: Arrow Tutorial
• Wikibooks: Haskell/Understanding arrows
• Arrows: A General Interface to Computation
• Hackage: Control.Arrow
• Programming with Arrows
• Generalising Monads to Arrows