Présentation
Dans Haskell, il est de coutume de travailler avec des effets comme foncteurs dont les objets sont des expressions qui nous intéressent en ce moment.
Quand nous voyons le type d'expression
Peut-être a , nous nous abstenons de l'existence réelle de certains
a , concentrant toute notre attention sur ce
a . La même histoire avec
Liste a - valeurs plurielles de
a ;
State sa -
a , selon un état actuel;
Soit ea -
a , ce qui peut renvoyer une erreur
e .
Avant de continuer, l'article utilisera plusieurs définitions:
type (:=) ta = ta
Par exemple:
Liste:. Peut-être: = a - cette expression est facile à imaginer, il s'agit d'une liste de valeurs dont l'existence est en cause.
De plus, à titre d'exemple, nous utiliserons quatre types communs:
Reader ,
State ,
Either ,
Maybe .
Compositions et transformateurs
La façon la plus évidente d'appliquer plus d'un effet à une expression est de simplement en incorporer un dans l'autre, c'est la composition habituelle des foncteurs. Dans les compositions, les effets n'ont aucun effet les uns sur les autres (sauf si des méthodes
transversales sont utilisées par-dessus). Et pour fusionner de nombreux effets en un seul, des transformateurs sont utilisés. Chaque méthode a ses avantages et ses inconvénients:
Compositions:
- Aucun type supplémentaire nécessaire pour les construire
- Il n'y a pas de méthode générale pour fusionner les effets avec les classes Functor / Applicative / Monad
- Tout se compose à merveille jusqu'à ce qu'il s'agisse de monades
Transformateurs:
- Vous permet de fusionner plusieurs effets en un seul
- Mais vous avez besoin d'un type distinct (le plus souvent un nouveau type)
- À l'aide de l' ascenseur, vous pouvez effectuer des calculs sur n'importe quelle couche de la pile de transformation.
- Mais vous ne pouvez pas prendre en compte les effets séparément, bien qu'il existe des fonctions spécialisées
Les transformateurs sont différents des compositions d'embrayage (je ne sais pas comment l'appeler différemment). Ayant une certaine composition, vous pouvez le transformer en transformateur et vice versa. Les schémas d'ancrage nous y aideront.
Schémas d'ancrage
Si nous examinons de plus près les types de transformateurs monades, nous pouvons identifier certains modèles:
newtype ReaderT rma = ReaderT { runReaderT :: r -> ma } newtype MaybeT ma = MaybeT { runMaybeT :: m (Maybe a) } newtype ExceptT ema = ExceptT { runExceptT :: m (Either ea)) } newtype StateT sma = StateT { runStateT :: s -> m (a,s) }
Les transformateurs décrivent un cas particulier de la façon dont l’effet défini et indéfini actuel doit être maillé.
Soit
t défini et
u indéfini, essayez:
Reader: r -> ua ===> (->) r :. u := a ===> t :. u := a
Certains effets sont assez complexes et peuvent être définis par la composition d'autres effets plus simples:
State: s -> u (a, s) ===> (->) s :. (,) s := a ==> t :. u :. t' := a
Si nous regardons de plus près les 3 premiers exemples, nous pouvons remarquer des modèles généraux: si dans
Reader , un certain effet en enveloppe un indéfini (le prend entre parenthèses, devient un objet d'un foncteur), puis avec
Soit et
Peut -
être c'est le contraire - un effet indéfini en termine un spécifique. Dans le cas de
State, nous plaçons même le foncteur entre deux effets définis plus simples.
Essayons d'exprimer ces modèles en types:
newtype TU tua = TU (t :. u := a) newtype UT tua = UT (u :. t := a) newtype TUT tut' a = TUT (t :. u :. t' := a)
Nous venons de définir des schémas d'ancrage - il s'agit d'une composition de foncteurs dans un wrapper qui indique la position d'un effet spécifique et indéfini.
En fait, les méthodes des transformateurs dont les noms commencent par
run suppriment simplement le wrapper du transformateur, retournant la composition des foncteurs. Nous décrivons une telle classe de types:
class Composition t where type Primary ta :: * run :: ta -> Primary ta
Maintenant, nous avons un moyen universel d'exécuter ces circuits:
instance Composition (TU tu) where type Primary (TU tu) a = t :. u := a run (TU x) = x instance Composition (UT tu) where type Primary (UT tu) a = u :. t := a run (UT x) = x instance Composition (TUT tu t') where type Primary (TUT tu t') a = t :. u :. t' := a run (TUT x) = x
Et les transformateurs? Ici, vous aurez également besoin d'une classe de type dans laquelle un schéma d'ancrage est prescrit pour un type particulier, la méthode d'
intégration est déclarée pour élever l'effet indéfini au niveau du transformateur et
construire pour construire un certain effet dans un transformateur:
class Composition t => Transformer t where type Schema (t :: * -> *) (u :: * -> *) = (r :: * -> *) | r -> tu embed :: Functor u => u ~> Schema tu build :: Applicative u => t ~> Schema tu type (:>) tua = Transformer t => Schema tua
Reste maintenant à déclarer les instances, commencez par
Maybe et
Soit :
instance Transformer Maybe where type Schema Maybe u = UT Maybe u embed x = UT $ Just <$> x build x = UT . pure $ x instance Transformer (Either e) where type Schema (Either e) u = UT (Either e) u embed x = UT $ Right <$> x build x = UT . pure $ x
Nous allons créer notre propre type pour
Reader , car il n'est pas dans la
base . Et il a également besoin d'une instance de la classe
Composition , car il s'agit d'un wrapper pour le foncteur flèche:
newtype Reader ea = Reader (e -> a) instance Composition (Reader e) where type Primary (Reader e) a = (->) ea run (Reader x) = x instance Transformer (Reader e) where type Schema (Reader e) u = TU ((->) e) u embed x = TU . const $ x build x = TU $ pure <$> run x
Faites quelque chose de similaire avec
State :
newtype State sa = State ((->) s :. (,) s := a) instance Composition (State s) where type Primary (State s) a = (->) s :. (,) s := a run (State x) = x instance Transformer (State s) where type Schema (State s) u = TUT ((->) s) u ((,) s) embed x = TUT $ \s -> (s,) <$> x build x = TUT $ pure <$> run x
À titre d'exemple
Il reste à tester cela sur les problèmes du monde réel - à titre d'exemple, nous allons écrire un programme qui calcule le placement correct de différents types de supports.
Définissez les types de parenthèses: ils peuvent être ouverts et fermés; et ont également différents styles:
data Shape = Opened | Closed data Style = Round | Square | Angle | Curly
Les autres symboles de notre programme ne sont pas intéressants:
data Symbol = Nevermind | Bracket Style Shape
Nous définissons également une liste d'erreurs que notre programme peut rencontrer:
data Stumble = Deadend (Int, Style)
De quels effets notre programme a-t-il besoin? Nous devons conserver une liste de crochets en attente de vérification et nous devons nous arrêter à la première erreur rencontrée. Nous fabriquons un transformateur:
State [(Int, Style)] :> Either Stumble := ()
L'algorithme est simple: nous parcourons la structure avec des crochets indexés, si après le passage nous n'avons pas rencontré d'erreur et que nous avons encore les crochets en l'état, alors le crochet ouvert n'en a pas de fermé:
checking :: Traversable t => t (Int, Symbol) -> Either Stumble () checking struct = run (traverse proceed struct) [] >>= \case (s : _, _) -> Left . Logjam $ s where ([], _) -> Right ()
Nous nous souvenons de tout crochet ouvert, comparons tout fermé au dernier ouvert mémorisé:
proceed :: (Int, Symbol) -> State [(Int, Style)] :> Either Stumble := () proceed (_, Nevermind) = pure () proceed (n, Bracket style Opened) = build . modify . (:) $ (n, style) procceed (n, Bracket closed Closed) = build get >>= \case []-> embed $ Left . Deadend $ (n, closed) ((m, opened) : ss) -> if closed /= opened then embed . Left $ Mismatch (m, opened) (n, closed) else build $ put ss where
Conclusion
En utilisant des schémas d'ancrage, ayant une certaine composition de foncteurs, nous pouvons les transformer en transfomères et vice versa. Malheureusement, une telle astuce ne fonctionnera pas avec la mère des monades - les suites. Et tout cela parce qu'ils ne peuvent pas être imaginés comme une composition de foncteurs, mais c'est possible comme une composition de professeurs ... Et pourtant, c'est une histoire complètement différente.
Code de bibliothèque sur Github |
Documentation de piratage |
Exemple de parenthèse