Quand les types supérieurs sont-ils utiles?

Je fais du développement en F # depuis un moment et j'aime ça. Cependant, un mot à la mode dont je sais qu'il n'existe pas en F # est celui des types de type supérieur. J'ai lu de la documentation sur les types plus élevés et je pense comprendre leur définition. Je ne sais tout simplement pas pourquoi ils sont utiles. Quelqu'un peut-il fournir des exemples de ce que les types de type supérieur facilitent dans Scala ou Haskell, qui nécessitent des solutions de contournement en F #? Aussi pour ces exemples, quelles seraient les solutions de contournement sans types de type supérieur (ou vice-versa en F #)? Peut-être que je suis tellement habitué à le contourner que je ne remarque pas l'absence de cette fonctionnalité.

(Je pense) J'obtiens que la place myList |> List.map fou myList |> Seq.map f |> Seq.toListles types supérieurs vous permettent d'écrire simplement myList |> map fet cela retournera un fichier List. C'est génial (en supposant que c'est correct), mais cela semble un peu mesquin? (Et cela ne pourrait-il pas être fait simplement en autorisant la surcharge de fonctions?) De Seqtoute façon, je convertis généralement en tout ce que je veux par la suite. Encore une fois, je suis peut-être trop habitué à contourner ce problème. Mais y a-t-il un exemple où les types de types plus élevés vous sauvent vraiment en frappes ou en sécurité de type?

Donc, le type d'un type est son type simple. Par exemple, Inta kind, *ce qui signifie qu'il s'agit d'un type de base et peut être instancié par des valeurs. Par une définition vague du type de type supérieur (et je ne suis pas sûr de savoir où F # trace la ligne, alors incluons-le simplement) les conteneurs polymorphes sont un excellent exemple d'un type de type supérieur.

data List a = Cons a (List a) | Nil

Le constructeur de type Lista kind * -> *ce qui signifie qu'il doit recevoir un type concret pour aboutir à un type concret: List Intpeut avoir des habitants comme [1,2,3]mais Listlui-même ne le peut pas.

Je vais supposer que les avantages des conteneurs polymorphes sont évidents, mais il * -> *existe des types de types plus utiles que les conteneurs. Par exemple, les relations

data Rel a = Rel (a -> a -> Bool)

ou analyseurs

data Parser a = Parser (String -> [(a, String)])

les deux ont aussi du genre * -> *.

Nous pouvons cependant aller plus loin dans Haskell en ayant des types avec des types d'ordre encore plus élevé. Par exemple, nous pourrions rechercher un type avec kind (* -> *) -> *. Un exemple simple de ceci pourrait être celui Shapequi essaie de remplir un conteneur de type * -> *.

data Shape f = Shape (f ())

[(), (), ()] :: Shape List

Ceci est utile pour caractériser les Traversables dans Haskell, par exemple, car ils peuvent toujours être divisés en leur forme et leur contenu.

split :: Traversable t => t a -> (Shape t, [a])

Comme autre exemple, considérons un arbre paramétré sur le type de branche dont il dispose. Par exemple, un arbre normal pourrait être

data Tree a = Branch (Tree a) a (Tree a) | Leaf

Mais nous pouvons voir que le type de branche contient a Pairde Tree as et nous pouvons donc extraire ce morceau du type de manière paramétrique

data TreeG f a = Branch a (f (TreeG f a)) | Leaf

data Pair a = Pair a a
type Tree a = TreeG Pair a

Ce TreeGconstructeur de type a kind (* -> *) -> * -> *. Nous pouvons l'utiliser pour créer d'autres variantes intéressantes comme unRoseTree

type RoseTree a = TreeG [] a

rose :: RoseTree Int
rose = Branch 3 [Branch 2 [Leaf, Leaf], Leaf, Branch 4 [Branch 4 []]]

Ou pathologiques comme un MaybeTree

data Empty a = Empty
type MaybeTree a = TreeG Empty a

nothing :: MaybeTree a
nothing = Leaf

just :: a -> MaybeTree a
just a = Branch a Empty

Ou un TreeTree

type TreeTree a = TreeG Tree a

treetree :: TreeTree Int
treetree = Branch 3 (Branch Leaf (Pair Leaf Leaf))

Un autre endroit où cela apparaît est dans les "algèbres de foncteurs". Si nous supprimons quelques couches d'abstrait, cela pourrait être mieux considéré comme un pli, tel que sum :: [Int] -> Int. Les algèbres sont paramétrées sur le foncteur et le porteur . Le foncteur a du genre * -> *et le genre de transporteur *si tout à fait

data Alg f a = Alg (f a -> a)

a du genre (* -> *) -> * -> *. Algutile en raison de sa relation avec les types de données et les schémas de récursivité construits sur eux.

-- | The "single-layer of an expression" functor has kind `(* -> *)`
data ExpF x = Lit Int
            | Add x x
            | Sub x x
            | Mult x x

-- | The fixed point of a functor has kind `(* -> *) -> *`
data Fix f = Fix (f (Fix f))

type Exp = Fix ExpF

exp :: Exp
exp = Fix (Add (Fix (Lit 3)) (Fix (Lit 4))) -- 3 + 4

fold :: Functor f => Alg f a -> Fix f -> a
fold (Alg phi) (Fix f) = phi (fmap (fold (Alg phi)) f)

Enfin, bien qu'ils soient théoriquement possibles, je n'ai jamais vu de constructeur de type encore plus élevé. Nous voyons parfois des fonctions de ce type comme mask :: ((forall a. IO a -> IO a) -> IO b) -> IO b, mais je pense que vous devrez fouiller dans le prologue de type ou la littérature typée de manière dépendante pour voir ce niveau de complexité dans les types.

Considérez la Functorclasse de type dans Haskell, où fest une variable de type de type supérieur:

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

Ce que dit cette signature de type, c'est que fmap modifie le paramètre de type d'un fde aà b, mais laisse ftel quel. Donc, si vous utilisez fmapsur une liste, vous obtenez une liste, si vous l'utilisez sur un analyseur, vous obtenez un analyseur, et ainsi de suite. Et ce sont des garanties statiques au moment de la compilation.

Je ne connais pas F #, mais considérons ce qui se passe si nous essayons d'exprimer l' Functorabstraction dans un langage comme Java ou C #, avec héritage et génériques, mais pas de génériques de type supérieur. Premier essai:

interface Functor<A> {
    Functor<B> map(Function<A, B> f);
}

Le problème avec ce premier essai est qu'une implémentation de l'interface est autorisée à renvoyer n'importe quelle classe implémentant Functor. Quelqu'un pourrait écrire une méthode FunnyList<A> implements Functor<A>dont la mapméthode renvoie un autre type de collection, ou même quelque chose d'autre qui n'est pas du tout une collection mais qui est toujours un Functor. De plus, lorsque vous utilisez la mapméthode, vous ne pouvez pas invoquer de méthodes spécifiques à un sous-type sur le résultat à moins que vous ne le réduisiez au type que vous attendez réellement. Nous avons donc deux problèmes:

1. Le système de types ne nous permet pas d'exprimer l'invariant selon lequel la mapméthode renvoie toujours la même Functorsous-classe que le récepteur.
2. Par conséquent, il n'y a pas de manière statiquement sûre d'appeler une non- Functorméthode sur le résultat de map.

Il existe d'autres méthodes plus compliquées que vous pouvez essayer, mais aucune d'entre elles ne fonctionne vraiment. Par exemple, vous pouvez essayer d'augmenter le premier essai en définissant des sous-types Functorqui restreignent le type de résultat:

interface Collection<A> extends Functor<A> {
    Collection<B> map(Function<A, B> f);
}

interface List<A> extends Collection<A> {
    List<B> map(Function<A, B> f);
}

interface Set<A> extends Collection<A> {
    Set<B> map(Function<A, B> f);
}

interface Parser<A> extends Functor<A> {
    Parser<B> map(Function<A, B> f);
}

// …

Cela aide à interdire aux implémenteurs de ces interfaces plus étroites de renvoyer le mauvais type de Functorde la mapméthode, mais comme il n'y a pas de limite au nombre d' Functorimplémentations que vous pouvez avoir, il n'y a pas de limite au nombre d'interfaces plus étroites dont vous aurez besoin.

( EDIT: Et notez que cela ne fonctionne que parce qu'il Functor<B>apparaît comme le type de résultat, et donc les interfaces enfants peuvent le restreindre. Donc, AFAIK, nous ne pouvons pas restreindre les deux utilisations de Monad<B>dans l'interface suivante:

interface Monad<A> {
    <B> Monad<B> flatMap(Function<? super A, ? extends Monad<? extends B>> f);
}

Dans Haskell, avec des variables de type de rang supérieur, c'est (>>=) :: Monad m => m a -> (a -> m b) -> m b.)

Une autre tentative consiste à utiliser des génériques récursifs pour essayer de faire en sorte que l'interface restreigne le type de résultat du sous-type au sous-type lui-même. Exemple de jouet:

/**
 * A semigroup is a type with a binary associative operation.  Law:
 *
 * > x.append(y).append(z) = x.append(y.append(z))
 */
interface Semigroup<T extends Semigroup<T>> {
    T append(T arg);
}

class Foo implements Semigroup<Foo> {
    // Since this implements Semigroup<Foo>, now this method must accept 
    // a Foo argument and return a Foo result. 
    Foo append(Foo arg);
}

class Bar implements Semigroup<Bar> {
    // Any of these is a compilation error:

    Semigroup<Bar> append(Semigroup<Bar> arg);

    Semigroup<Foo> append(Bar arg);

    Semigroup append(Bar arg);

    Foo append(Bar arg);

}

Mais ce type de technique (qui est plutôt obscur pour votre développeur OOP ordinaire, diable pour votre développeur fonctionnel ordinaire également) ne peut toujours pas exprimer la Functorcontrainte souhaitée non plus:

interface Functor<FA extends Functor<FA, A>, A> {
    <FB extends Functor<FB, B>, B> FB map(Function<A, B> f);
}

Le problème ici est que cela ne se limite pas FBà avoir le même Fque FA- de sorte que lorsque vous déclarez un type List<A> implements Functor<List<A>, A>, la mapméthode peut toujours renvoyer un NotAList<B> implements Functor<NotAList<B>, B>.

Dernier essai, en Java, en utilisant des types bruts (conteneurs non paramétrés):

interface FunctorStrategy<F> {
    F map(Function f, F arg);
} 

Ici, Fseront instanciés vers des types non paramétrés comme just Listou Map. Cela garantit que a FunctorStrategy<List>ne peut renvoyer qu'un List- mais vous avez abandonné l'utilisation de variables de type pour suivre les types d'éléments des listes.

Le cœur du problème ici est que les langages comme Java et C # ne permettent pas aux paramètres de type d'avoir des paramètres. En Java, si Test une variable de type, vous pouvez écrire Tet List<T>, mais pas T<String>. Les types de type supérieur suppriment cette restriction, de sorte que vous puissiez avoir quelque chose comme ça (pas complètement pensé):

interface Functor<F, A> {
    <B> F<B> map(Function<A, B> f);
}

class List<A> implements Functor<List, A> {

    // Since F := List, F<B> := List<B>
    <B> List<B> map(Function<A, B> f) {
        // ...
    }

}

Et en abordant ce bit en particulier:

(Je pense) J'obtiens que la place myList |> List.map fou myList |> Seq.map f |> Seq.toListles types supérieurs vous permettent d'écrire simplement myList |> map fet cela retournera un fichier List. C'est génial (en supposant que c'est correct), mais cela semble un peu mesquin? (Et cela ne pourrait-il pas être fait simplement en autorisant la surcharge de fonctions?) De Seqtoute façon, je convertis généralement en tout ce que je veux par la suite.

Il existe de nombreux langages qui généralisent l'idée de la mapfonction de cette façon, en la modélisant comme si, au fond, la cartographie concernait des séquences. Cette remarque est dans cet esprit: si vous avez un type qui prend en charge la conversion vers et depuis Seq, vous obtenez l'opération de carte "gratuitement" en réutilisant Seq.map.

Dans Haskell, cependant, la Functorclasse est plus générale que cela; il n'est pas lié à la notion de séquences. Vous pouvez implémenter fmappour des types qui n'ont pas de bonne correspondance avec les séquences, comme les IOactions, les combinateurs d'analyseurs, les fonctions, etc.:

instance Functor IO where
    fmap f action =
        do x <- action
           return (f x)

 -- This declaration is just to make things easier to read for non-Haskellers 
newtype Function a b = Function (a -> b)

instance Functor (Function a) where
    fmap f (Function g) = Function (f . g)  -- `.` is function composition

Le concept de «mapping» n'est pas vraiment lié aux séquences. Il est préférable de comprendre les lois des foncteurs:

(1) fmap id xs == xs
(2) fmap f (fmap g xs) = fmap (f . g) xs

Très informellement:

1. La première loi dit que le mappage avec une fonction d'identité / noop revient à ne rien faire.
2. La deuxième loi dit que tout résultat que vous pouvez produire en mappant deux fois, vous pouvez également le produire en mappant une fois.

C'est pourquoi vous souhaitez fmapconserver le type, car dès que vous obtenez des mapopérations qui produisent un type de résultat différent, il devient beaucoup plus difficile de faire des garanties comme celle-ci.

Je ne veux pas répéter les informations dans d'excellentes réponses déjà ici, mais il y a un point clé que j'aimerais ajouter.

Vous n'avez généralement pas besoin de types de type supérieur pour implémenter une monade ou un foncteur particulier (ou un foncteur applicatif, ou une flèche, ou ...). Mais faire cela, c'est manquer l'essentiel.

En général, j'ai trouvé que lorsque les gens ne voient pas l'utilité des foncteurs / monades / quoi que ce soit, c'est souvent parce qu'ils pensent à ces choses une à la fois . Les opérations Functor / monad / etc n'ajoutent vraiment rien à une seule instance (au lieu d'appeler bind, fmap, etc., je pourrais simplement appeler les opérations que j'ai utilisées pour implémenter bind, fmap, etc.). Ce que vous voulez vraiment pour ces abstractions, c'est que vous puissiez avoir du code qui fonctionne de manière générique avec n'importe quel foncteur / monad / etc.

Dans un contexte où ce code générique est largement utilisé, cela signifie que chaque fois que vous écrivez une nouvelle instance de monade, votre type accède immédiatement à un grand nombre d'opérations utiles qui ont déjà été écrites pour vous . C'est le point de voir des monades (et des foncteurs, et ...) partout; non pas pour que je puisse utiliser bindplutôt que concatet mappour implémenter myFunkyListOperation(ce qui ne me rapporte rien en soi), mais plutôt pour que lorsque j'en ai besoin myFunkyParserOperationet que myFunkyIOOperationje puisse réutiliser le code que j'ai vu à l'origine en termes de listes car il est en fait monad-générique .

Mais pour faire abstraction d'un type paramétré comme une monade avec sécurité de type , vous avez besoin de types de type supérieur (comme expliqué dans d'autres réponses ici).

Pour une perspective plus spécifique à .NET, j'ai écrit un article de blog à ce sujet il y a quelque temps. Le point crucial est que, avec les types de type supérieur, vous pouvez potentiellement réutiliser les mêmes blocs LINQ entre IEnumerableset IObservables, mais sans types de type supérieur, c'est impossible.

Le plus proche que vous pourriez obtenir (j'ai compris après avoir publié le blog) est de faire votre propre IEnumerable<T>et IObservable<T>et les deux étendues d'un IMonad<T>. Cela vous permettrait de réutiliser vos blocs LINQ s'ils sont indiqués IMonad<T>, mais ce n'est plus du type sécurisé car cela vous permet de mélanger et de faire correspondre IObservableset IEnumerablesdans le même bloc, ce qui, même si cela peut sembler intriguant d'activer cela, vous simplement obtenir un comportement indéfini.

J'ai écrit un article plus tard sur la façon dont Haskell rend cela facile. (Un no-op, vraiment - restreindre un bloc à un certain type de monade nécessite du code; l'activation de la réutilisation est la valeur par défaut).

L'exemple le plus utilisé de polymorphisme de type supérieur dans Haskell est l' Monadinterface. Functoret Applicativesont de nature supérieure de la même manière, donc je vais montrer Functorafin de montrer quelque chose de concis.

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

Maintenant, examinez cette définition, en regardant comment la variable de type fest utilisée. Vous verrez que fcela ne peut pas signifier un type qui a de la valeur. Vous pouvez identifier les valeurs dans cette signature de type car ce sont des arguments et des résultats d'une fonction. Donc, les variables de type aet bsont des types qui peuvent avoir des valeurs. Il en va de même pour les expressions de type f aet f b. Mais pas flui-même. fest un exemple de variable de type supérieur. Étant donné que *c'est le genre de types qui peuvent avoir des valeurs, fdoit avoir le genre * -> *. Autrement dit, il faut un type qui peut avoir des valeurs, car nous savons d'après un examen précédent que aet bdoit avoir des valeurs. Et nous savons aussi que f aetf b doit avoir des valeurs, il renvoie donc un type qui doit avoir des valeurs.

Cela rend le futilisé dans la définition d' Functorune variable de type supérieur.

Les interfaces Applicativeet Monadajoutent plus, mais elles sont compatibles. Cela signifie qu'ils fonctionnent également sur des variables de type avec kind * -> *.

Travailler sur des types de type supérieur introduit un niveau supplémentaire d'abstraction - vous n'êtes pas limité à la création d'abstractions sur les types de base. Vous pouvez également créer des abstractions sur des types qui modifient d'autres types.