Les fonctions n'ont pas que des types: ce sont des types. Et des genres. Et trie. Aidez à reconstituer un esprit renversé

Question

J'ai été faire mon habituel "Lire un chapitre de LYAH avant d'aller au lit" de routine, avoir l'impression que mon cerveau était en pleine expansion avec tous les exemples de code. À ce point, j'étais convaincu que j'ai compris le noyau de l'awesomeness de Haskell, et maintenant juste eu à comprendre les bibliothèques standard et type de classes afin que je puisse commencer à écrire de véritables logiciels.

J'ai donc été lire le chapitre sur les foncteurs applicatifs, lorsque tout à coup le livre affirmé que les fonctions ne se contente pas d'avoir des types, ils sont des types, et peuvent être traités en tant que tels (Par exemple, en faisant d'eux des instances de classes de type). (->) est un constructeur de type comme les autres.

Mon esprit a soufflé encore une fois, et j'ai immédiatement sauté hors du lit, au démarrage de l'ordinateur, est allé à GHCi et découvert les suivantes:

Prelude> :k (->)
(->) :: ?? -> ? -> *

• Que diable veut-il dire?
• Si (->) est un constructeur de type, ce sont la valeur des constructeurs? Je peux faire une supposition, mais elle n'aurait aucune idée de comment le définir traditionnels data (->) ... = ... | ... | ... format. Il est assez facile de faire cela avec n'importe quel autre type constructeur: data Either a b = Left a | Right b. Je soupçonne mon incapacité à s'exprimer sous cette forme est liée à la extrêmement bizarre type de signature.
• Qu'ai-je viens de tombé sur? Plus kinded types ont des signatures comme * -> * -> *. Venez pour penser à elle... (->) s'affiche dans le genre des signatures trop! Est-ce à dire que non seulement c'est un constructeur de type, mais aussi à une sorte de constructeur? Est-ce lié à la question des marques dans le type de signature?

J'ai lu quelque part (souhaite que je pourrais trouver encore une fois, Google ne parvient pas moi) au sujet d'être en mesure d'étendre les systèmes de type arbitraire de Valeurs, pour les Types de Valeurs, de Sortes de Types de Sortes de Sortes, à quelque chose d'autre de toutes Sortes, à quelque chose d'autre, quelque chose de elses, et ainsi de suite indéfiniment. Est-ce reflète dans le type de signature pour la (->)? Parce que j'ai également exécuter dans la notion de la Lambda cube et le calcul des constructions sans prendre vraiment le temps de les étudier, et si je me souviens bien il est possible de définir des fonctions qui prennent des types et des types de retour, les valeurs et les valeurs de retour, prenez les types et les valeurs de retour, et de prendre des valeurs des types de retour.

Si je devais prendre une deviner le type de signature, pour une fonction qui prend une valeur et renvoie un type, je serais probablement exprimer comme ceci:

a -> ?

ou, éventuellement,

a -> *

Bien que je ne vois pas les fondamentaux immuables raison pour laquelle le deuxième exemple, on ne pouvait pas facilement être interprétée comme une fonction à partir d'une valeur de type a à une valeur de type *, où * est juste un type synonyme de chaîne ou quelque chose.

Le premier exemple exprime mieux une fonction dont le type transcende une signature de type dans mon esprit: "une fonction qui prend une valeur de type a et renvoie à quelque chose qui ne peut être exprimée comme un type."

Answer 1

Vous touchez donc de nombreux points intéressants dans votre question, donc je suis peur que cela va être une réponse longue :)

Sorte de (->)

Le genre d' (->) est * -> * -> *, si l'on fait abstraction de la boxity GHC inserts. Mais il n'y a pas de circularité, le ->s dans la type d' (->) sont des sortes de flèches, pas de fonction de flèches. En effet, à distinguer ces flèches peuvent être écrits comme (=>), puis le genre d' (->) est * => * => *.

On peut considérer (->) comme un constructeur de type, ou peut-être plutôt un type de l'opérateur. De même, (=>) pourrait être considéré comme une sorte d'opérateur, et comme vous le suggérez dans votre question, nous devons aller à un 'niveau' jusqu'à. Nous de retour plus tard dans la section au-Delà de Sortes, mais d'abord:

Comment la situation se regarde dans un dépendante tapé langue

Vous vous demandez comment le type de signature de chercher une fonction qui prend un valeur et renvoie un type. C'est impossible de le faire en Haskell: les fonctions ne peuvent pas les types de retour! Vous pouvez simuler ce comportement à l'aide de les classes de type et le type de familles, mais laissez-nous pour l'illustration du changement la langue de l'dépendante tapé langue Agda. C'est un langue avec la même syntaxe que Haskell où la jonglerie types avec des valeurs est une seconde nature.

Pour avoir quelque chose à travailler avec, nous de définir un type de données de naturel des chiffres, pour la commodité de la représentation unaire comme dans L'Arithmétique De Peano. Types de données sont écrites dans GADT style:

data Nat : Set where
    Zero : Nat
    Succ : Nat -> Nat

Ensemble est équivalent à * en Haskell, le "type" de toutes les (petites) types de comme les nombres Naturels. Cela nous indique que le type d' Natest Set, alors qu'en Haskell, Nat n'aurait pas un type, il aurait un genre, à savoir *. Dans Agda il n'y a pas de genres, mais tout a un type.

Nous pouvons maintenant écrire une fonction qui prend une valeur et renvoie un type. Ci-dessous est une fonction qui prend un nombre naturel n et un type, et de fait itère l' List constructeur n appliqué à cette type. (En Agda, [a] est généralement écrites List a)

listOfLists : Nat -> Set -> Set
listOfLists Zero     a = a
listOfLists (Succ n) a = List (listOfLists n a)

Quelques exemples:

listOfLists Zero               Bool = Bool
listOfLists (Succ Zero)        Bool = List Bool
listOfLists (Succ (Succ Zero)) Bool = List (List Bool)

Nous pouvons maintenant faire un map fonction qui fonctionne sur listsOfLists. Nous avons besoin de prendre un nombre naturel qui est le nombre d'itérations de la liste de constructeur. La base de cas où le nombre est Zero, alors listOfList est juste de l'identité et de nous appliquer la fonction. L'autre est la liste vide, et la liste vide est retournée. L'étape de cas est un peu déplacer impliquant: nous appliquons mapN à la tête de la liste, mais il a une couche de moins de nidification, et mapN pour le reste de la liste.

mapN : {a b : Set} -> (a -> b) -> (n : Nat) ->
       listOfLists n a -> listOfLists n b
mapN f Zero     x         = f x
mapN f (Succ n) []        = []
mapN f (Succ n) (x :: xs) = mapN f n x :: mapN f (Succ n) xs

Dans le type d' mapN, l' Nat argument est nommé n, de sorte que le reste de le type peut en dépendre. C'est donc un exemple d'un type qui dépend de la valeur.

_{Comme une note de côté, il y a aussi deux autres variables nommées ici, à savoir le premier des arguments, a et b, de type Set. Type les variables sont implicitement universellement quantifiée en Haskell, mais ici, nous avons besoin de sort, et de préciser leur type, à savoir Set. Les parenthèses sont là pour les rendre invisibles dans l' définition, car ils sont toujours résultant des autres arguments.}

Jeu abstrait

Vous vous demandez ce que les constructeurs d' (->) sont. Une chose à noter c'est qu' Set (ainsi que * en Haskell) est abstraite: vous ne pouvez pas de correspondance de modèle sur elle. Donc, ce qui est illégal Agda:

cheating : Set -> Bool
cheating Nat = True
cheating _   = False

Encore une fois, vous pouvez simuler le filtrage sur les types des constructeurs en Haskell en utilisant le type de familles, un canoical exemple est donné sur Brent Yorgey du blog. Pouvons-nous définir le -> dans l'Agda? Puisque nous ne pouvons types de retour de fonctions, nous pouvons définir une version propre d' -> comme suit:

_=>_ : Set -> Set -> Set
a => b = a -> b

(opérateurs infixes sont écrites _=>_ plutôt que d' (=>)) Ce définition a très peu de contenu, et est très similaire à faire un synonyme de type en Haskell:

type Fun a b = a -> b

Au-delà de types: les Tortues tout le chemin vers le bas

Comme promis ci-dessus, tout en Agda a un type, mais alors le type d' _=>_ doit avoir un type! Ce touche à votre point de de sortes, qui est, pour ainsi dire, une couche Ensemble ci-dessus (le genre). Dans Agda cela s'appelle Set1:

FunType : Set1
FunType = Set -> Set -> Set

Et en fait, il y a toute une hiérarchie d'entre eux! Est le type de les "petits" de types: les types de données en haskell. Mais ensuite nous avons Set1, Set2, Set3, et ainsi de suite. Set1 est le genre de types qui mentionne Set. Cette hiérarchie est d'éviter des incohérences, telles que Girard le paradoxe.

Comme l'a remarqué dans votre question, -> est utilisé pour les types et les genres dans Haskell, et la même notation est utilisée pour la fonction de l'espace à tous les niveaux dans Agda. Ceci doit être considéré comme un construit dans le type d'opérateur, et les constructeurs sont lambda abstraction (ou de la fonction les définitions). Cette hiérarchie de types est similaire à la mise en Le système F omega, et plus d'informations peuvent être trouvées dans les chapitres de Pierce Types et des Langages de Programmation.

Pure type systems

Dans Agda, les types peuvent dépendre des valeurs et fonctions des types de retour, comme illustré ci-dessus, et nous avons également eu une hiérarchie de les types. L'examen systématique des différents systèmes de l'lambda des calculs est étudiée plus en détail dans le plus Pur Type de Systèmes. Une bonne de référence est Lambda-Calculs avec des Types par Barendregt, où PTS sont introduites à la page 96, et de nombreux exemples à la page 99 et suivantes. Vous pouvez aussi lire plus sur le lambda cube là.

Answer 2

Tout d'abord, l' ?? -> ? -> * type est un GHC-extension spécifique. L' ? et ?? sont juste là pour s'en occuper "unboxed" types, qui se comportent différemment à partir de seulement * (ce qui doit être mis en boîte, autant que je sache). Donc, ?? peut être n'importe quel type normal ou un décaissement type (par exemple, Int#); ? peut être soit de personnes ou d'un décaissement de tuple. Il n'y a plus d'informations ici: Haskell Bizarre Types: Type d' (->) est ?? -> ? -> *

Je pense qu'une fonction ne peut pas retourner un unboxed type parce que les fonctions sont paresseux. Depuis un paresseux valeur est une valeur ou un thunk, il doit être encadré. Coffret signifie simplement qu'il est un pointeur plutôt que de juste valeur: c'est comme Integer() vs int en Java.

Puisque vous êtes probablement ne va pas être à l'aide de unboxed types de LYAH au niveau du code, vous pouvez imaginer que le type d' -> est juste * -> * -> *.

Depuis l' ? et ?? sont fondamentalement juste plus générales version de *, ils n'ont rien à faire avec des tris ou quelque chose comme ça.

Cependant, depuis -> est juste un constructeur de type, vous pouvez en fait partiellement l'appliquer; par exemple, (->) e est une instance de l' Functor et Monad. Trouver comment écrire ces cas, c'est un bon esprit d'exercices d'étirement.

Autant que la valeur des constructeurs aller, ils doivent juste être lambdas (\ x ->) ou les déclarations de fonction. Étant donné que les fonctions sont fondamentales pour la langue, qu'ils obtiennent leur propre syntaxe.