Quel est le but de Rank2Types?

Je ne suis pas très compétent en Haskell, donc cela pourrait être une question très facile.

Quelle limitation de la langue est-ce que Rank2Types résout? Les fonctions dans Haskell ne prennent-elles pas déjà en charge les arguments polymorphes?

Les fonctions dans Haskell ne prennent-elles pas déjà en charge les arguments polymorphes?

Ils le font, mais uniquement du rang 1. Cela signifie que, bien que vous puissiez écrire une fonction qui prend différents types d’arguments sans cette extension, vous ne pouvez pas écrire une fonction qui utilise son argument comme différents types dans le même appel.

Par exemple, la fonction suivante ne peut pas être saisie sans cette extension car g est utilisé avec différents types d’arguments dans la définition de f :

 fg = g 1 + g "lala" 

Notez qu’il est parfaitement possible de passer une fonction polymorphe comme argument à une autre fonction. Donc quelque chose comme un map id ["a","b","c"] est parfaitement légal. Mais la fonction peut seulement l’utiliser comme monomorphe. Dans l’exemple, la map utilise id comme si elle avait le type Ssortingng -> Ssortingng . Et bien sûr, vous pouvez également passer une fonction monomorphe simple du type donné au lieu de id . Sans rank2types, il n’ya aucun moyen pour une fonction d’exiger que son argument soit une fonction polymorphe et donc de ne pas pouvoir l’utiliser comme fonction polymorphe.

Il est difficile de comprendre le polymorphism de rang supérieur à moins d’étudier directement le système F , car Haskell est conçu pour vous en cacher les détails dans un souci de simplicité.

Mais en gros, l’idée de base est que les types polymorphes n’ont pas vraiment la a -> b qu’ils ont dans Haskell; en réalité, ils ressemblent à ceci, toujours avec des quantificateurs explicites:

 id :: ∀aa → a id = Λt.λx:tx 

Si vous ne connaissez pas le symbole “∀”, il se lit comme “pour tous”; ∀x.dog(x) signifie “pour tout x, x est un chien.” “Λ” est un lambda majuscule, utilisé pour effectuer une parsing sur les parameters de type; La deuxième ligne indique que id est une fonction qui prend un type t , puis renvoie une fonction paramétrée par ce type.

Vous voyez, dans System F, vous ne pouvez pas simplement appliquer une fonction comme celle-ci à une valeur immédiatement; Vous devez d’abord appliquer la fonction function à un type afin d’obtenir une fonction λ que vous appliquez à une valeur. Donc par exemple:

 (Λt.λx:tx) Int 5 = (λx:Int.x) 5 = 5 

Standard Haskell (c’est-à-dire Haskell 98 et 2010) vous simplifie la tâche en ne disposant d’aucun de ces quantificateurs de type, applications majuscules et applications de type, mais en coulisse lorsque GHC parsing le programme pour la compilation. (Je pense que c’est tout à la compilation, sans surcharge).

Mais le traitement automatique de Haskell signifie que cela suppose que “∀” n’apparaît jamais dans la twig gauche d’un type de fonction (“→”). Rank2Types et RankNTypes désactivent ces ressortingctions et vous permettent de remplacer les règles par défaut de Haskell pour savoir où les insérer.

Pourquoi voudriez-vous faire cela? Parce que le System F complet et sans ressortingction est très puissant, il peut faire beaucoup de choses intéressantes. Par exemple, le masquage de type et la modularité peuvent être implémentés en utilisant des types de rang supérieur. Prenons par exemple une ancienne fonction simple du type rank-1 suivant (pour définir la scène):

 f :: ∀r.∀a.((a → r) → a → r) → r 

Pour utiliser f , l’appelant doit d’abord choisir les types à utiliser pour r et a , puis fournir un argument du type résultant. Vous pouvez donc choisir r = Int et a = Ssortingng :

 f Int Ssortingng :: ((Ssortingng → Int) → Ssortingng → Int) → Int 

Mais maintenant, comparez cela au type de rang supérieur suivant:

 f' :: ∀r.(∀a.(a → r) → a → r) → r 

Comment fonctionne une fonction de ce type? Eh bien, pour l’utiliser, vous devez d’abord spécifier le type à utiliser pour r . Disons que nous choisissons Int :

 f' Int :: (∀a.(a → Int) → a → Int) → Int 

Mais maintenant, le ∀a est à l’ intérieur de la flèche de la fonction, vous ne pouvez donc pas choisir le type à utiliser pour a ; Vous devez appliquer f' Int à une fonction type du type approprié. Cela signifie que l’implémentation de f' choisit quel type utiliser pour a , pas l’appelant de f' . Sans types de rang supérieur, l’appelant choisit toujours les types.

A quoi cela sert-il? Eh bien, pour beaucoup de choses en fait, mais une idée est que vous pouvez l’utiliser pour modéliser des choses comme la programmation orientée object, où les “objects” regroupent des données cachées avec certaines méthodes qui fonctionnent sur les données cachées. Ainsi, par exemple, un object avec deux méthodes – l’une qui renvoie un Int et l’autre qui renvoie un Ssortingng , pourrait être implémenté avec ce type:

 myObject :: ∀r.(∀a.(a → Int, a -> Ssortingng) → a → r) → r 

Comment cela marche-t-il? L’object est implémenté sous la forme d’une fonction contenant des données internes de type caché a . Pour utiliser réellement l’object, ses clients transmettent une fonction “callback” que l’object appellera avec les deux méthodes. Par exemple:

 myObject Ssortingng (Λa. λ(length, name):(a → Int, a → Ssortingng). λobjData:a. name objData) 

Ici, nous invoquons, en gros, la deuxième méthode de l’object, celle dont le type est a → Ssortingng pour un inconnu a . Eh bien, inconnu des clients de myObject ; mais ces clients savent, à partir de la signature, qu’ils pourront y appliquer l’une ou l’autre des deux fonctions et obtenir soit un Int soit un Ssortingng .

Pour un exemple réel de Haskell, RankNTypes le code que j’ai écrit quand je me suis enseigné RankNTypes . Cela implémente un type appelé ShowBox qui regroupe une valeur d’un type caché avec son instance de classe Show . Notez que dans l’exemple ci-dessous, je fais une liste de ShowBox dont le premier élément a été créé à partir d’un nombre et le second d’une chaîne. Comme les types sont masqués en utilisant les types de rang supérieur, cela ne viole pas la vérification de type.

 {-# LANGUAGE RankNTypes #-} {-# LANGUAGE ImpredicativeTypes #-} type ShowBox = forall b. (forall a. Show a => a -> b) -> b mkShowBox :: Show a => a -> ShowBox mkShowBox x = \k -> kx -- | This is the key function for using a 'ShowBox'. You pass in -- a function @k@ that will be applied to the contents of the -- ShowBox. But you don't pick the type of @k@'s argument--the -- ShowBox does. However, it's ressortingcted to picking a type that -- implements @Show@, so you know that whatever type it picks, you -- can use the 'show' function. runShowBox :: forall b. (forall a. Show a => a -> b) -> ShowBox -> b -- Expanded type: -- -- runShowBox -- :: forall b. (forall a. Show a => a -> b) -- -> (forall b. (forall a. Show a => a -> b) -> b) -- -> b -- runShowBox k box = box k example :: [ShowBox] -- example :: [ShowBox] expands to this: -- -- example :: [forall b. (forall a. Show a => a -> b) -> b] -- -- Without the annotation the comstackr infers the following, which -- breaks in the definition of 'result' below: -- -- example :: forall b. [(forall a. Show a => a -> b) -> b] -- example = [mkShowBox 5, mkShowBox "foo"] result :: [Ssortingng] result = map (runShowBox show) example 

PS: pour quiconque lit ceci, qui se demande comment ExistentialTypes de GHC peut se forall , je crois que la raison en est que ce type de technique est utilisé en coulisse.

La réponse de Luis Casillas donne beaucoup d’informations intéressantes sur la signification des types de rang 2, mais je vais juste développer un point qu’il n’a pas abordé. Exiger qu’un argument soit polymorphe ne lui permet pas seulement d’être utilisé avec plusieurs types; cela restreint également ce que cette fonction peut faire avec ses arguments et comment elle peut produire son résultat. Autrement dit, cela donne moins de flexibilité à l’appelant. Pourquoi voudriez-vous faire ça? Je commencerai par un exemple simple:

Supposons que nous ayons un type de données

 data Country = BigEnemy | MediumEnemy | PunyEnemy | TradePartner | Ally | BestAlly 

et nous voulons écrire une fonction

 fg = launchMissilesAt $ g [BigEnemy, MediumEnemy, PunyEnemy] 

cela prend une fonction qui est censée choisir l’un des éléments de la liste qui lui est donnée et renvoyer une action IO qui lance des missiles sur cette cible. On pourrait donner un type simple:

 f :: ([Country] -> Country) -> IO () 

Le problème est que nous pourrions accidentellement courir

 f (\_ -> BestAlly) 

et alors nous aurions de gros problèmes! Donner un type polymorphe de rang 1

 f :: ([a] -> a) -> IO () 

n’aide pas du tout, car nous choisissons le type a lorsque nous appelons f , et nous le spécialisons simplement dans Country et utilisons à nouveau notre \_ -> BestAlly . La solution consiste à utiliser un type de rang 2:

 f :: (forall a . [a] -> a) -> IO () 

Maintenant, la fonction que nous transmettons doit être polymorphe, donc \_ -> BestAlly ne va pas taper check! En fait, aucune fonction renvoyant un élément ne figurant pas dans la liste qui lui est donnée sera vérifiée (bien que certaines fonctions qui entrent dans des boucles infinies ou produisent des erreurs et ne retournent donc jamais le feront).

Ce qui précède est bien sûr artificiel, mais une variante de cette technique est essentielle pour sécuriser le ST monad.

Les types de rang supérieur ne sont pas aussi exotiques que les autres réponses l’ont fait. Croyez-le ou non, de nombreux langages orientés object (y compris Java et C #!) Les contiennent. (Bien sûr, personne dans ces communautés ne les connaît sous le nom effrayant de “types de rang supérieur”.)

L’exemple que je vais vous donner est une mise en œuvre du modèle Visitor, que j’utilise tout le temps dans mon travail quotidien. Cette réponse ne vise pas à introduire le modèle de visiteur. cette connaissance est facilement disponible ailleurs .

Dans cette application RH imaginaire, nous souhaitons travailler avec des employés qui peuvent être des employés permanents à temps plein ou des entrepreneurs temporaires. Ma variante préférée du pattern Visitor (et en fait celle qui concerne RankNTypes ) paramètre le type de retour du visiteur.

 interface IEmployeeVisitor { T Visit(PermanentEmployee e); T Visit(Contractor c); } class XmlVisitor : IEmployeeVisitor { /* ... */ } class PaymentCalculator : IEmployeeVisitor { /* ... */ } 

Le fait est que plusieurs visiteurs avec des types de retour différents peuvent tous opérer sur les mêmes données. Cela signifie que IEmployee doit exprimer aucune opinion quant à ce que T devrait être.

 interface IEmployee { T Accept(IEmployeeVisitor v); } class PermanentEmployee : IEmployee { // ... public T Accept(IEmployeeVisitor v) { return v.Visit(this); } } class Contractor : IEmployee { // ... public T Accept(IEmployeeVisitor v) { return v.Visit(this); } } 

Je souhaite attirer votre attention sur les types. IEmployeeVisitor que IEmployeeVisitor quantifie universellement son type de retour, alors que IEmployee quantifie dans sa méthode Accept , c’est-à-dire à un rang supérieur. Traduire clunkily de C # en Haskell:

 data IEmployeeVisitor r = IEmployeeVisitor { visitPermanent :: PermanentEmployee -> r, visitContractor :: Contractor -> r } newtype IEmployee = IEmployee { accept :: forall r. IEmployeeVisitor r -> r } 

Alors voilà Les types de rang supérieur apparaissent en C # lorsque vous écrivez des types contenant des méthodes génériques.

Les diapositives du cours Haskell de Bryan O’Sullivan à Stanford m’ont aidé à comprendre les Rank2Types .

Pour ceux qui sont familiers avec les langages orientés object, une fonction de rang supérieur est simplement une fonction générique qui attend comme argument une autre fonction générique.

Par exemple, dans TypeScript, vous pouvez écrire:

 type WithId = T & { id: number } type Identifier = (obj: T) => WithId type Identify = (obj: TObj, f: Identifier) => WithId 

Voir comment le type de fonction générique Identify exige une fonction générique du type Identifier ? Cela rend Identify une fonction de rang supérieur.