Les listes peuvent-elles être définies d’une manière spéciale afin qu’elles contiennent des éléments de types différents ?

Question

Dans https://www.seas.harvard.edu/courses/cs152/2019sp/lectures/lec18-monads.pdf il est écrit que

Un type $ au$ list est le type de listes avec des éléments de type $ au$

Pourquoi une liste doit-elle contenir des éléments du même type ?Pourquoi ne peut-il pas contenir des éléments de types différents ?Existe-t-il un moyen de définir une liste de manière polymorphe dans le calcul lambda typé, afin qu'elle prenne des éléments de n'importe quel type ?

Peut-on alors utiliser la monade List sur des listes, définies de manière polymorphe ?

Answer 1

La réponse courte est que $ \ tau \ \ text {liste} $ est défini comme constructeur de type, ainsi que des règles pour Formation et élimination, et donc nous pourrions aussi définir un constructeur de type permettant de définir des termes de différents types pour former une seule "liste distincte variable". Toutefois, les listes ne peuvent pas prendre différents types dans la définition donnée, simplement parce qu'ils sont définis par rapport à un seul type. Dans les deux cas, l'ajout de listes ou des listes de type variable, consiste à étendre la classification $ \ lambda $ -calculus, comme listes de tout genre n'existe pas dans la présentation habituelle.

Si nous avons un système de type légèrement plus riche que celui de $ \ lambda $ -Calculus, nous pouvons encoder des listes de type variable à l'aide de standard $ \ tau \ \ text {liste} $ s.

• Si nous avons une forme de Subtyping , nous pouvons stocker des termes de différents types, comme longtemps comme ils partagent un supertype. Toutefois, lorsque nous proposons des éléments de projet hors de la liste, nous ne pouvons plus dire spécifiquement quel type ils devaient commencer (cela peut être familier à la programmation orientée objet), c'est donc un peu limitée.
• Si nous avons Types de somme dépendante (également appelé $ \ sigma $ -Types) et un Type de l'univers $ \ mathcal u $ (c.-à-d. Un "type de types"), nous pouvons former le type $ ( \ Sigma_ {A: \ mathcal u} a) \ \ texte {liste} $ , dont les éléments sont des paires composées d'un type $ a $ et a terme de ce type.

Enfin, je vais simplement noter que le polymorphisme ne nous aide pas si nous voulons des listes hétérogènes: cela nous permet de manipuler des listes homogènes pour différentes $ \ tau $ plus efficacement. Les types polymorphes doivent être uniforme en quelque sorte, c'est pourquoi nous avons besoin de dépendance ici. < / p>

---

Pour répondre à une question de suivi: si nous avons deux listes triés variablement à l'aide de l'approche de type dépendant, nous pouvons concaténer et aplatir les listes comme avec des listes ordinaires.

• La $ \ MATHRM {LISTE} $ MONAAD a une opération $ \ mathrm {join} $ (Dans la langue de HASKELLL), une liste de listes distinctes variablement, $$ l= [[(a, a), (B, B)], [(C , c), (d, d)]]: (\ sigma_ {x: \ mathcal u} x) \ \ text {liste de liste} $$ Nous pouvons effectuer $ \ mathrm {rejoindre} $ Pour obtenir une nouvelle liste: $$ \ mathrm {join} (L)= [(A, A), (B, B) , (C, c), (d, d)]: (\ sigma_ {x: \ mathcal u} x) \ \ texte {liste} $$
• De même, $ \ TAU \ \ TEXT {Liste} $ peut être équipé d'une opération de concaténation $ + \! + $ , donc compte tenu des deux listes de l'exemple précédent, nous pouvons les concaténer pour un résultat similaire: $$ [(a, a), (b, b)] \ {+ \! +} \ [(c, c), (d, d)]= [(A , a), (b, b), (c, c), (d, d)]: (\ sigma_ {x: \ mathcal u} x) \ \ text {liste} $$

Answer 2

Non, ce n'est pas possible, du moins pas de manière utile.Pensez au type de head serait.Lorsque chaque élément a le même type, head a le type $ au\;\mathsf{liste} o au$.Sans cette garantie, il n'y aurait aucun moyen d'écrire un type cohérent pour head.Pour que le type de liste soit utile, nous voulons pouvoir tirer des conclusions utiles sur le type de sortie de head est;et cela nécessite que tous les éléments de la liste aient le même type.

je suppose que tu pourrait définir une "liste" d'une autre manière, mais cela ne serait pas utile non plus (vous ne pourriez pas raisonner sur le type de valeurs que vous en extrayez avec head) ou cela ne correspondrait pas à ce que les informaticiens appelleraient une "liste".

Answer 3

Vous ne pouvez pas définir utilement un type $\mathsf{liste}$ cela n'indique pas le type de ses éléments.Cela ne veut pas dire que vous ne pouvez pas avoir de listes contenant des éléments de différents types :c'est toujours un $ au \, \mathsf{liste}$, mais vous pouvez mettre la partie « contenir des éléments de différents types » dans le champ $ au$.

(Ces idées de base étaient déjà dans D.W. et varkorles réponses.Il est important de réaliser que ces réponses ne sont pas contradictoires !Ils examinent différents aspects de la situation dans son ensemble.)

Si le système de types vous permet de définir un type $\mathsf{liste}$ qui peut contenir des éléments de n'importe quel type, alors considérez le type de retour d'un destructeur comme $\mathsf{tête}$ ou $\mathsf{ntième}$, ou le type de l'argument de fonction à $\mathsf{plier}$.Vous n'avez aucune information sur le type des éléments, ils devraient donc autoriser n'importe quel type.Cela signifie que par exemple $\lambda x.\mathsf{head}(\mathsf{cons}(x, \mathsf{nil}))$ ne vous rendra pas une valeur du même type que $x$ (ou $x \, \mathsf{option}$, de sorte que $\mathsf{tête}$ peut revenir $\mathsf{Aucun}$ sur des listes vides).Mais alors, de quoi reviens-tu $\mathsf{tête}$?

• Si $\mathsf{tête}$ permet à l'appelant de spécifier n'importe quel type de retour, alors le système de types est pratiquement inutile, car il permet des coercitions arbitraires entre les types via $\lambda x.\mathsf{head}(\mathsf{cons}(x, \mathsf{nil}))$.C'est inutile pour la logique puisque le Correspondance Curry-Howard mappe une coercition arbitraire entre les types pour que chaque proposition implique toutes les autres propositions, vous avez donc une logique incohérente.
• Sinon, vous ne pouvez pas récupérer une valeur du type d'origine via $\lambda x.\mathsf{head}(\mathsf{cons}(x, \mathsf{nil}))$.Vous pourrez donc peut-être créer des listes, mais vous ne pourrez pas en extraire des éléments.

Un exemple concret qui démontre en fait les deux comportements ci-dessus est premières versions de Java, avant qu'il n'y ait génériques.Java possède à la fois un système de types statiques et un système de types dynamiques.Dans le système de types statiques, n'importe quelle valeur¹ peut être contrainte de manière transparente à Object, parce que Object est considéré comme un supertype de tout.Vous pouvez donc mettre n'importe quelle valeur dans un List.Mais ce que vous en retirez, c'est la valeur originale convertie en Object, pas la valeur d'origine elle-même.Dans le système de types dynamiques, vous pouvez contraindre n'importe quel type à n'importe quel autre type, donc en pratique, pour extraire une valeur d'une liste, vous la contraignez au type souhaité.Mais avoir des coercitions va à l’encontre de l’objectif d’un système de types.Ce problème est la principale raison pour laquelle Java a acquis des génériques :ils permettent à la langue d'avoir $ au \, \mathsf{liste}$ au lieu de $\mathsf{liste}$ (ou en notation Java, List<T> au lieu de List).

Tout simplement parce qu'une liste contient un type d'éléments :$ au \, \mathsf{liste}$ est une liste d'éléments de type $ au$  – ne signifie pas que vous ne pouvez pas faire en sorte de placer des valeurs de types différents dans la même liste.Presque tous les langages permettant de définir un type de liste le font en autorisant type de données algébrique définitions, quelque chose comme ceci :$$ au \, \mathsf{list} ::= \mathsf{nil} \mid \mathsf{cons} \: au\:( au \, \mathsf{liste}) $$Supposons que vous souhaitiez mettre des entiers et des chaînes dans la même liste.Définir un type$$ U ::= \mathsf{I} \:\mathsf{int} \mid \mathsf{S} \ :\mathsf{chaîne} $$Maintenant $U \, \mathsf{liste}$ est le type de listes qui peuvent contenir un mélange d'entiers et de chaînes, par ex. $[\mathsf{I}(3), \mathsf{S}( exttt{"foo"}), \mathsf{I}(4)]$.

Vous pouvez créer des listes hétérogènes de cette manière dans la mesure où le système de types autorise les types hétérogènes.Notez que « listes hétérogènes » n'est pas tout à fait correct :la liste elle-même est homogène :c'est une liste d'éléments de type $U$.L'hétérogénéité est dans le type $U$.Pour mettre un élément dans la liste, vous appliquez un constructeur de $U$ d'abord.Après avoir retiré un élément de la liste, appliquez un destructeur de $U$ pour obtenir la valeur d'origine avec son type d'origine.

Vous pouvez le faire avec n’importe quel type pris en charge par le langage.Si vous souhaitez une liste complètement hétérogène, vous avez besoin d'un langage prenant en charge un type « any ».C'est Object en Java, par exemple.Les types fortement typés peuvent avoir un type « any » s’ils contiennent les informations de type nécessaires au moment de l’exécution.Java le fait tout le temps.Les langages typés statiquement (tels que OCaml et d'autres dialectes ML, Haskell, Clean, Swift ou Rust) peuvent le faire avec un $\mathsf{dyn}$ type dont la représentation d’exécution contient le type de la valeur.Avec un tel type, $\mathsf{dyn} \, \mathsf{liste}$ est un type de liste qui peut contenir une valeur de n'importe quel type.Ce type coexiste avec d'autres types de listes tels que $\mathsf{int} \, \mathsf{liste}$ (où les éléments de la liste ne contiennent pas d'informations de type d'exécution).

Une approche connexe pour créer des structures de données hétérogènes est types existentiels.Les types existentiels vous permettent de conditionner un type avec une valeur de ce type : $(\existe au :P( au).a)$ où $un$ est une expression d'un certain type $T$ tel que $P(T)$ est vrai.Par exemple, $\mathsf{dyn}$ peut être modélisé comme un cas particulier où $P$ est vrai pour tous les types (un existentiel illimité).Une utilisation courante des types existentiels est de dire que $ au$ est un enregistrement, un module ou une classe avec des éléments ou des méthodes particuliers, sans donner tous les détails :les types existentiels sont un moyen de modéliser des types abstraits.Avec un existentiel limité, vous pouvez toujours faire des choses utiles avec la valeur même sans informations de type d'exécution (par ex.vous pouvez appeler les méthodes qui $P$ décrit), mais n'obtient pas le type d'origine.Une liste dont les éléments ont un type existentiel $T_E = (\existe au \ldots)$ peut être considérée comme une liste hétérogène (car ses éléments ont des types « réels » différents), mais elle reste homogène dans le sens où si vous récupérez une valeur de la liste, tout ce que vous savez est son type de package $T_E$.

Si la langue a types dépendants, vous pouvez empaqueter une valeur avec son type de manière à permettre de récupérer la valeur d'origine : $\mathsf{package} ::= \sum_{ au:\mathsf{TYPE}} au$ où $\mathsf{TYPE}$ est le type de types.C'est un type de somme dépendante où le premier composant se trouve être un type.Le $\mathsf{paquet}$ type est un moyen d'implémenter des existentiels illimités dans un langage typé de manière dépendante.Vous pouvez construire des existentiels bornés en ajoutant des contraintes sur $ au$.Encore une fois, on peut construire des listes hétérogènes dans le sens où un $\mathsf{package} \, \mathsf{liste}$ contient des éléments dont les types « réels » sont différents, mais la liste elle-même est homogène dans le sens où chaque élément de la liste a le type $\mathsf{paquet}$.Comme pour les types existentiels, vous ne pouvez pas extraire une valeur d'une liste et récupérer directement son « vrai » type.Il est possible de détruire une valeur de type $\mathsf{paquet}$ en appliquant la projection du deuxième élément, mais tout ce que vous savez du résultat, c'est que son type est la projection du premier élément : $p :\mathsf{package} \vdash \pi_2(p) :\pi_1(p)$.

Jusqu’à présent, nous avons vu que dans un système de types non dégénérés, les listes sont homogènes.Il est possible de construire des listes hétérogènes, mais le constructeur du type de liste lui-même est homogène :l'hétérogénéité vient du type d'élément.Dans un langage qui possède à la fois des types de données algébriques et des types dépendant d'un entier (ou de quelque chose d'isomorphe aux naturels), il est possible de définir un type de liste véritablement hétérogène.Étant donné une famille de types $(T_n)_{n \in \mathbb{N}}$, vous pouvez définir le type de listes dont $n$l'élément a le type $T_n$.Voici une telle définition dans la langue du calcul des constructions inductives, spécifiquement dans la syntaxe Coq.Tout d’abord, je définis un exemple de famille de types indexés par un entier : tuple A n est le type de n-tuples d'éléments dont les composants ont tous le type A.Pour garder la définition simple, tous les tuples ont une valeur supplémentaire U au début du type d'unité.Ensuite je définis le type inductif hlist_ qui est paramétré à la fois par une famille de types T et un entier n, qui est une liste hétérogène dont kl'élément a le type n + k.Le paramètre n est nécessaire de garder la définition constructive.Enfin, je montre quelques exemples de termes de type hlist (tuple bool), c'est-à-dire des listes dont nl'élément est un nth-tuple d'éléments de bool valeurs (avec U ajouté).

Inductive unit : Type := U : unit.
Fixpoint tuple (A : Type) (n : nat) : Type :=
  match n with
    | 0 => unit
    | S m => (tuple A m) * A
  end.

Inductive hlist_ (T : nat -> Type) n :=
  | Hnil : hlist_ T n
  | Hcons : (T n) -> hlist_ T (S n) -> hlist_ T n.
Definition hlist T := hlist_ T 0.

Check (Hcons (tuple bool) 0 U (Hnil _ _) : hlist (tuple bool)).
Check (Hcons (tuple bool) 0 U (Hcons _ 1 (U, true) (Hnil _ _)) : hlist (tuple bool)).
Check (Hcons (tuple bool) 0 U (Hcons _ 1 (U, true) (Hcons _ 2 (U, true, true) (Hnil _ _))) : hlist (tuple bool)).

¹ _{Sauf pour certains types de données primitifs, en fait, mais ce n'est pas important ici.Quand je dis « n'importe lequel » à propos de Java dans cette réponse, je parle uniquement d'objets, et non de types de données primitifs.}