Considérez cet ADT:

data Property f a = Property String (f a) | Zilch
  deriving Show

Qu'est-ce que f ici? Est-ce une fonction agissant sur a? Est-ce une «fonction de type»? L'instructeur a dit que Haskell a un langage de type complet Turing ... alors dans quel cas les types peuvent aussi avoir des fonctions, je suppose?

*Main> var = Property "Colors" [1,2,3,4]
*Main> :t var
var :: Num a => Property [] a

Comment f se comporte comme [] ici? Puisque [] est le constructeur de la liste vide, est-ce que f sera toujours le constructeur vide le plus extérieur pour le type de a comme dans les exemples suivants?

*Main> var = Property "Colors" [(1,"Red"),(2,"Blue")]
*Main> :t var
var :: Num t => Property [] (t, [Char])

*Main> var = Property "Colors" (1,"Red")
*Main> :t var
var :: Num t => Property ((,) t) [Char]

Le dernier, je ne comprends pas tout à fait, mais si quelqu'un a dit que Haskell a déduit le constructeur vide pour ce tuple, je suis d'accord pour l'acheter. D'autre part,

*Main> var = Property "Colors" 20
*Main> :t var
var :: Num (f a) => Property f a

Qu'est-ce que f ici? Ça ne peut pas être l'identité parce que id :: a -> a mais nous avons besoin de (f a).

J'ai réussi à faire de mon ADT un foncteur avec:

instance Functor f => Functor (Property f) where
  fmap fun (Property name a) = Property name (fmap fun a)
  fmap g Zilch               = Zilch 

Donc quelque chose comme ce qui suit fonctionne

*Main> var = Property "Colors" [1,2,3,4]
*Main> fmap (+1) var
Property "Colors" [2,3,4,5]

Mais que se passe-t-il si je le donne à l'exemple précédent d'un tuple?

Je recherche vraiment des réponses explicatives (j'ai vu Haskell pendant à peine deux mois dans un cours d'été), pas des références à des choses comme FlexibleContexts pour permettre ... disons fmap de travailler sur arbitraire {{X2} }.

8
ITA 20 juil. 2017 à 02:46

2 réponses

Meilleure réponse

Vous avez été confus par le fait (déroutant) que [] signifie deux choses différentes dans des contextes différents dans Haskell, ce qui vous a rendu difficile d'interpréter le reste de vos expériences.

Au niveau de la valeur [] se trouve en effet le constructeur vide pour les listes. Mais lorsque vous avez demandé le type de Property "Colors" [1,2,3,4] et vu Property [] a, vous recherchez une expression de type , pas une expression de valeur. Il n'y a pas de liste vide au niveau du type. 1 Au lieu de cela, [] est le constructeur de type pour le type de liste. Vous pouvez avoir [Int] (le type de listes d'entiers), [Bool] (le type de listes de bools) ou [a] (le type polymorphe de listes de a) ; [] est la chose qui est appliquée à Int, Bool et a dans ces exemples.

Vous pouvez en fait écrire [Int] comme [] Int si vous le souhaitez, même si cela semble étrange, donc vous ne voyez généralement [] qu'au niveau du type lorsque vous voulez l'utiliser sans application.

Regardons à nouveau votre déclaration de données:

data Property f a = Property String (f a) | Zilch

Sur le côté gauche, vous avez déclaré la forme du type Property; Property f a forme un type. Sur le côté droit, vous déclarez la forme des valeurs qui entrent dans ce type, en listant les constructeurs de valeur possibles (Property et Zilch) et les types de " slots "dans ces constructeurs (aucun pour Zilch; un slot de type String et un autre de type f a, pour Property).

Donc, à partir de là, nous pouvons dire que quels que soient f et a, l'expression de type f a (f appliquée à a) doit former un type qui a des valeurs . Mais f n'a pas à être (en fait il ne peut pas être) un type normal de valeurs à lui seul! Il n'y a pas d'emplacement de type f dans le constructeur de valeur Property.

Un exemple beaucoup plus clair à utiliser aurait été celui-ci:

*Main> var = Property "Stuff" (Just True)
*Main> :t var
var :: Property Maybe Bool

Si vous ne le connaissez pas, Maybe est un type intégré dont la déclaration ressemble à ceci:

data Maybe a = Just a | Nothing

C'est bien pour cet exemple car nous n'utilisons pas le même nom au niveau du type et au niveau de la valeur, ce qui évite toute confusion lorsque vous essayez d'apprendre comment les choses fonctionnent.

Just True est une valeur de type Maybe Bool. Au niveau de la valeur, nous avons le constructeur de données Just appliqué à la valeur True. Au niveau du type, nous avons le Maybe constructeur de type appliqué au type Bool. Les valeurs Maybe Bool sont placées dans l'emplacement f a du constructeur de valeurs Property, ce qui correspond parfaitement: f est Maybe et a est {{X12 }}.

Revenons donc à votre exemple d'origine:

*Main> var = Property "Colors" [1,2,3,4]
*Main> :t var
var :: Num a => Property [] a

Vous remplissez la case f a avec [1, 2, 3, 4]. C'est une liste d'une sorte de nombre, donc ce sera Num t => [t]. Donc le a dans f a est le t (avec une contrainte Num qui doit arriver), et le f est le type de liste constructeur []. Ce [] est comme Maybe, pas comme Nothing.

*Main> var = Property "Colors" (1,"Red")
*Main> :t var
var :: Num t => Property ((,) t) [Char]

Ici, la case f a est remplie avec (1, "Red"), qui est de type Num t => (t, [Char]) (en se souvenant que String est juste une autre façon d'écrire [Char]). Maintenant, pour comprendre cela, nous devons devenir un peu capricieux. Oubliez la contrainte pour le moment et concentrez-vous simplement sur (t, [Char]). D'une manière ou d'une autre, nous devons interpréter cela comme quelque chose appliqué à autre chose, afin de pouvoir le faire correspondre à f a. Eh bien, il s'avère que bien que nous ayons une syntaxe spéciale pour les types de tuple (comme (a, b)), ils sont vraiment comme les ADT ordinaires que vous pourriez déclarer sans la syntaxe spéciale. Un type à 2 tuples est un constructeur de type que nous pouvons écrire (,) appliqué à deux autres types, dans ce cas t et [Char]. Et nous pouvons utiliser des constructeurs de type partiellement appliqués, ainsi nous pouvons penser à (,) appliqué à t comme une unité, et cette unité appliquée à [Char]. Nous pouvons écrire cette interprétation comme une expression de type Haskell ((,) t) [Char], mais je ne suis pas sûr que ce soit plus clair. Mais en fin de compte, nous pouvons faire correspondre cela à f a en prenant la première "unité" (,) t comme f et [Char] comme a. Ce qui nous donne alors Property ((,) t) [Char] (seulement nous devons également remettre la contrainte Num t que nous avions oubliée plus tôt).

Et enfin celui-ci:

*Main> var = Property "Colors" 20
*Main> :t var
var :: Num (f a) => Property f a

Ici, nous remplissons la case f a avec 20, une sorte de nombre. Nous n'avons pas spécifié exactement le type du nombre, donc Haskell est prêt à croire qu'il pourrait s'agir de n'importe quel type de la classe Num. Mais nous avons toujours besoin que le type ait une "forme" que nous pouvons faire correspondre avec f a: un constructeur de type appliqué à un autre type. Et c'est toute l'expression de type f a qui doit correspondre au type de 20, donc c'est ce qui a une contrainte Num. Mais nous n'avons rien dit d'autre sur ce que pourraient être f ou a, et 20 peut par tout type qui répond à une contrainte Num , donc cela peut être n'importe quel Num (f a) => f a que nous voulons pour cela, d'où la raison pour laquelle le type de votre var est toujours polymorphe dans f et a (juste avec la contrainte ajoutée).

Vous n'avez peut-être vu que des types numériques comme Integer, Int, Double, etc., et vous vous demandez donc comment il pourrait y avoir un f a qui est un nombre; tous ces exemples ne sont que des types de base uniques, pas quelque chose qui s'applique à quelque chose. Mais vous pouvez écrire vos propres instances Num, donc Haskell ne suppose jamais qu'un type donné (ou une forme de type) ne pourrait être un nombre, il se plaindra simplement si vous essayez réellement de utilisez-le et il ne trouve pas d'instance Num. Donc parfois, vous obtenez des choses comme celle-ci qui sont probablement des erreurs, mais Haskell accepte (pour l'instant) avec un type Num sur une chose étrange à laquelle vous ne vous attendiez pas.

Et en fait, il y a il y a déjà des types dans les bibliothèques intégrées qui ont un structore au niveau du type composé et une instance Num. Un exemple est le type Ratio pour représenter des nombres fractionnaires sous forme de rapports de deux entiers. Vous pouvez avoir un Ratio Int ou un Ratio Integer, par exemple:

Main*> 4 :: Ratio Int
4 % 1

Vous pourriez donc dire:

*Main> var = Property "Colors" (20 :: Ratio Integer)
*Main> :t var
var :: Property Ratio Integer

1 En fait, il peut y en avoir, avec l'extension DataKinds activée pour autoriser les types qui reflètent la structure de presque toutes les valeurs, donc vous pouvez avoir des listes au niveau du type. Mais ce n'est pas ce qui se passe ici et ce n'est pas vraiment une fonctionnalité que vous pouvez utiliser jusqu'à ce que vous ayez une bonne maîtrise du fonctionnement des types et des valeurs dans vanilla Haskell, donc je vous recommande d'ignorer cette note de bas de page et de prétendre qu'elle n'existe pas encore .

10
Will Ness 20 juil. 2017 à 01:03

L'instructeur a dit que Haskell a un langage de type Turing complet ...

Tout d'abord, cette affirmation est erronée. Haskell n'a pas de système de type complet Turing. Il y a des extensions dans GHC pour le rendre Turing complet, mais Haskell pur n'a pas de système de type complet Turing.

Comment f se comporte comme [] ici? Puisque [] est le constructeur de la liste vide, est-ce que f sera toujours le constructeur vide le plus extérieur pour le type de a comme dans les exemples suivants?

Vous mélangez des constructeurs de type avec des constructeurs de valeur. Haskell a défini une liste comme suit:

data [] a = [] | a : ([] a)

Le gras est le [] constructeur de type , le non-gras est le constructeur de valeur. Si vous écrivez [] dans une signature de type, vous faites référence au type. Par exemple map a le type map :: (a -> b) -> [] a -> [] b.

Maintenant, comme nous l'avons vu dans la définition de data [], nous avons un paramètre de type . Nous devons appliquer le type [] à un autre type avant qu'il ne soit un type "concret". Donc le "méta-type" de [] est * -> *: il faut.

Il en est de même pour le type Property, il a un méta-type * -> * -> * car il nécessite deux paramètres de type. Property [] en revanche a un méta-type * -> *.

4
Willem Van Onsem 20 juil. 2017 à 00:16