43 votes

Quelle est la différence entre le polymorphisme paramétrique et les types supérieurs ?

Je suis presque sûr qu'ils ne sont pas les mêmes. Cependant, je suis embourbé dans la l'idée commune que "Rust ne supporte pas" les types de type plus élevé (HKT), mais offre au contraire polymorphisme paramétrique . J'ai essayé de m'y retrouver et de comprendre la différence entre les deux, mais je me suis de plus en plus empêtré.

D'après ce que j'ai compris, il y a sont Les types de type supérieur en Rust, au moins les bases. En utilisant l'annotation "*", un HKT a un type, comme par exemple * -> * . Par exemple, Maybe est de type * -> * et pourrait être implémenté comme ceci en Haskell.

data Maybe a = Just a | Nothing

Ici,

  • Maybe est un constructeur de type et doit être appliqué à un type concret pour devenir un type concret de type "*".
  • Just a y Nothing sont des constructeurs de données.

Dans les manuels sur Haskell, ce type est souvent utilisé comme exemple de type supérieur. Cependant, en Rust, il peut simplement être implémenté comme un enum, qui après tout est un type type de somme :

enum Maybe<T> {
    Just(T),
    Nothing,
}

Où est la différence ? D'après ce que j'ai compris, c'est un exemple parfait d'un type supérieur.

  1. Si en Haskell, ceci est utilisé comme un exemple de manuel de HKTs, pourquoi il est dit que Rust n'a pas de HKT ? Est-ce que le Maybe se qualifie comme un HKT ?
  2. Faut-il plutôt dire que Rust n'a pas entièrement soutenir HKT ?
  3. Quelle est la différence fondamentale entre HKT et le polymorphisme paramétrique ?

Cette confusion continue quand on regarde les fonctions, je peux écrire une fonction paramétrique qui prend un Maybe et, à ma connaissance, un HKT comme fonction. argument.

fn do_something<T>(input: Maybe<T>) {
    // implementation
}

Encore une fois, en Haskell, ce serait quelque chose comme

do_something :: Maybe a -> ()
do_something :: Maybe a -> ()
do_something _ = ()

ce qui conduit à la quatrième question.

  1. Où s'arrête exactement le soutien aux types supérieurs ? Quel est l'exemple exemple minimal pour que le système de types de Rust ne puisse pas exprimer HKT ?

Questions connexes :

J'ai parcouru un grand nombre de questions liées au sujet (y compris les liens qu'ils ont vers des articles de blog, etc.) mais je n'ai pas pu trouver de réponse à mes questions principales (1 et 2).

  1. En Haskell, les "types supérieurs" sont-ils *vraiment* des types ? Ou bien désignent-ils simplement des collections de types *concrets* et rien de plus ?
  2. Structure générique sur un type générique sans paramètre de type
  3. Types plus élevés en Scala
  4. Quels types de problèmes le "polymorphisme de type supérieur" permet-il de mieux résoudre ?
  5. Types de données abstraits et polymorphisme paramétrique en Haskell

Mise à jour

Merci pour les nombreuses bonnes réponses qui sont toutes très détaillées et qui m'ont beaucoup aidé. J'ai décidé d'accepter la réponse d'Andreas Rossberg car son explication m'a le plus aidé à me mettre sur la bonne voie. En particulier la partie concernant la terminologie.

J'étais vraiment enfermé dans le cycle de la pensée que tout ce qui est du genre * -> * ... -> * es supérieur . L'explication qui souligne la différence entre * -> * -> * y (* -> *) -> * était crucial pour moi.

8 votes

Je pense que ce que l'on veut dire par "Rust ne supporte pas les types de type supérieur" est qu'il ne peut pas abstrait sur elles, c'est-à-dire qu'on ne peut pas quantifier sur des variables de type de type * -> * ou plus.

3 votes

Oui, ce que Rust n'a pas, c'est un polymorphisme de type supérieur. Comme d'habitude, les gens sont très négligents avec le langage de manière confuse.

0 votes

Je ne suis pas sûr de bien comprendre ce que vous dites tous les deux. Voulez-vous dire que, par exemple, un type générique T doit être un type concret et ne peut pas être lui-même un type supérieur ? Autrement dit, quelque chose comme struct Baz<T<V>> {} ne fonctionnera pas ?

37voto

Andreas Rossberg Points 11897

Un peu de terminologie :

  • Le genre * est parfois appelé terrain . Vous pouvez le considérer comme un ordre 0.
  • Tout type de forme * -> * -> ... -> * avec au moins une flèche est premier ordre .
  • A ordre supérieur est celle qui comporte une "flèche imbriquée à gauche", par exemple, (* -> *) -> * .

El commander est essentiellement la profondeur de l'imbrication gauche des flèches, par exemple, (* -> *) -> * est de second ordre, ((* -> *) -> *) -> * est de troisième ordre, etc. (Pour information, la même notion s'applique aux types eux-mêmes : une fonction de deuxième ordre est une fonction dont le type a, par exemple, la forme (A -> B) -> C .)

Les types de type non-sol (ordre > 0) sont également appelés type constructeurs (et certains ouvrages ne font référence qu'aux types de type terrestre en tant que "types"). Un type (constructeur) de type supérieur est un type dont le type est d'ordre supérieur (ordre > 1).

Par conséquent, un type de type supérieur est un type qui prend un argument de type non-sol. Cela nécessiterait des variables de type de type non-ground, qui ne sont pas supportées dans de nombreux langages. Exemples en Haskell :

type Ground = Int
type FirstOrder a = Maybe a  -- a is ground
type SecondOrder c = c Int   -- c is a first-order constructor
type ThirdOrder c = c Maybe  -- c is second-order

Les deux derniers sont de nature plus élevée.

De même, polymorphisme supérieur décrit la présence de valeurs polymorphes (paramétriques) qui font abstraction de types qui ne sont pas fondés. Encore une fois, peu de langages supportent cela. Exemple :

f : forall c. c Int -> c Int  -- c is a constructor

L'affirmation selon laquelle Rust prend en charge le polymorphisme paramétrique "au lieu" des types de type supérieur n'a pas de sens. Les deux sont des dimensions différentes du paramétrage qui se complètent l'une l'autre. Et lorsque vous combinez les deux, vous obtenez un polymorphisme de type supérieur.

0 votes

Note : La rouille plans pour supporter une forme de polymorphisme de type supérieur via les Generic Associated Types. C'est-à-dire qu'un trait (classe de type) peut avoir des types associés (à remplir par l'implémenteur), et le plan est de les rendre polymorphes. Cette série de blogs de Niko Matsakis décrit cette fonctionnalité, qui s'appelait auparavant Constructeurs de types associés .

16voto

Carl Points 10866

Un exemple simple de ce que Rust ne peut pas faire est quelque chose comme la méthode Haskell Functor classe.

class Functor f where
    fmap :: (a -> b) -> f a -> f b

-- a couple examples:
instance Functor Maybe where
    -- fmap :: (a -> b) -> Maybe a -> Maybe b
    fmap _ Nothing  = Nothing
    fmap f (Just x) = Just (f x)

instance Functor [] where
    -- fmap :: (a -> b) -> [a] -> [b]
    fmap _ []     = []
    fmap f (x:xs) = f x : fmap f xs

Notez que les instances sont définies sur le constructeur du type, Maybe o [] au lieu du type entièrement appliqué Maybe a o [a] .

Ce n'est pas juste un tour de parloir. Il y a une forte interaction avec le polymorphisme paramétrique. Puisque les variables de type a y b dans le type fmap ne sont pas contraints par la définition de la classe, les instances de Functor ne peuvent pas changer leur comportement en fonction d'eux. C'est une propriété incroyablement forte dans le raisonnement sur le code à partir des types, et d'où vient une grande partie de la force du système de types de Haskell.

Il possède une autre propriété : vous pouvez écrire du code abstrait dans des variables de type supérieur. Voici quelques exemples :

focusFirst :: Functor f => (a -> f b) -> (a, c) -> f (b, c)
focusFirst f (a, c) = fmap (\x -> (x, c)) (f a)

focusSecond :: Functor f => (a -> f b) -> (c, a) -> f (c, b)
focusSecond f (c, a) = fmap (\x -> (c, x)) (f a)

J'admets que ces types commencent à ressembler à des absurdités abstraites. Mais ils s'avèrent très pratiques lorsque vous disposez de quelques aides qui tirent parti de l'abstraction de type supérieur.

newtype Identity a = Identity { runIdentity :: a }

instance Functor Identity where
    -- fmap :: (a -> b) -> Identity a -> Identity b
    fmap f (Identity x) = Identity (f x)

newtype Const c b = Const { getConst :: c }

instance Functor (Const c) where
    -- fmap :: (a -> b) -> Const c a -> Const c b
    fmap _ (Const c) = Const c

set :: ((a -> Identity b) -> s -> Identity t) -> b -> s -> t
set f b s = runIdentity (f (\_ -> Identity b) s)

get :: ((a -> Const a b) -> s -> Const a t) -> s -> a
get f s = getConst (f (\x -> Const x) s)

(Si j'ai fait des erreurs là-dedans, quelqu'un peut-il les corriger ? Je suis en train de réimplémenter le point de départ le plus basique de lens de la mémoire sans compilateur).

Les fonctions focusFirst y focusSecond peut être passé comme premier argument à l'un des deux get o set car la variable de type f dans leurs types peuvent être unifiés avec les types plus concrets de la section get y set . La possibilité de s'abstraire de la variable de type supérieur f permet aux fonctions d'une forme particulière d'être utilisées à la fois comme setters et getters dans des types de données arbitraires. Il s'agit de l'une des deux idées principales qui ont conduit à la création de l'outil de gestion des fonctions. lens bibliothèque. Elle ne pourrait pas exister sans ce type d'abstraction.

(Pour ce que cela vaut, l'autre idée clé est que définir les lentilles comme une fonction comme cela permet à la composition de lentilles d'être une simple composition de fonction).

Donc non, il y a plus que la simple possibilité d'accepter une variable de type. La partie importante est la possibilité d'utiliser des variables de type qui correspondent à des constructeurs de type, plutôt qu'à un type concret (même inconnu).

10voto

Federico Sawady Points 514

Je vais le reprendre : un type supérieur est juste une fonction d'ordre supérieur au niveau du type.

Mais prenez une minute :

Pensez à monad transformateurs :

newtype StateT s m a :: * -> (* -> *) -> * -> *

Ici,

- s is the desired type of the state
- m is a functor, another monad that StateT will wrap
- a is the return type of an expression of type StateT s m

Qu'est-ce que le type supérieur ?

m :: (* -> *)

Parce qu'il prend un type de type * et retourne une sorte de type * .

C'est comme une fonction sur les types, c'est-à-dire un constructeur de type de type

* -> *

Dans des langages comme Java, vous ne pouvez pas faire

class ClassExample<T, a> {
    T<a> function()
}

En Haskell, T aurait le genre *->* Mais un type Java (c'est-à-dire une classe) ne peut pas avoir de paramètre de type de ce type, un type de type supérieur.

De plus, si vous ne le savez pas, en Haskell de base, une expression doit avoir un type qui a le genre * c'est-à-dire un "type concret". Tout autre type comme * -> * .

Par exemple, vous ne pouvez pas créer une expression de type Maybe . Il s'agit de types appliqués à un argument tel que Maybe Int , Maybe String etc. En d'autres termes, des constructeurs de types entièrement appliqués.

9voto

chepner Points 54078

Le polymorphisme paramétrique désigne simplement la propriété selon laquelle la fonction ne peut utiliser aucune caractéristique particulière d'un type (ou genre) dans sa définition ; il s'agit d'une boîte noire complète. L'exemple standard est length :: [a] -> Int qui ne fonctionne qu'avec le structure de la liste, et non les valeurs particulières stockées dans la liste.

L'exemple standard de HKT est le Functorfmap :: (a -> b) -> f a -> f b . Contrairement à lengtha a du genre * , f a du genre * -> * . fmap également présente un polymorphisme paramétrique, car fmap ne peut faire usage d'aucune propriété de l'un ou l'autre a o b dans sa définition.

fmap présente également un polymorphisme ad hoc, car la définition puede être adapté au constructeur de type spécifique f pour lequel il est défini. En d'autres termes, il existe des définitions distinctes de fmap para f ~ [] , f ~ Maybe etc. La différence est que f est "déclarée" comme faisant partie de la définition de la classe de type, plutôt que de faire partie de la définition de l'élément fmap . (En effet, les classes de types ont été ajoutées pour supporter un certain degré de polymorphisme ad hoc. Sans classes de types, uniquement le polymorphisme paramétrique existe. Vous pouvez écrire une fonction qui supporte un type de béton ou tout type concret, mais pas une collection plus petite entre les deux).

Prograide.com

Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.

Powered by:

X