Types et éléments de conteneur associés

Eh bien, le problème est que ce n'est pas clair ce que le Functor révisé est censé signifier. Par exemple, considérez ByteString. Un ByteString ne peut être mappé qu'en remplaçant chaque élément Word8 par un élément du même type. Mais {[5] } est pourparamétrique structures mappables. Il y a vraiment deux notions contradictoires de cartographie ici:

• mapping rigide (c'est-à-dire transformer chaque élément d'une structure sans changer son type)
• cartographie paramétrique (c'est-à-dire transformer chaque élément d'une structure à n'importe quel type)

Donc, dans ce cas, vous ne pouvez pas expliquer au système de type ce que vous vouliez dire, car cela n'a pas beaucoup de sens. Vous pouvez, cependant, changer ce que vous voulez dire:)

La cartographie rigide est facile à exprimer avec les familles de types:

class RigidMap f where
  type Element f :: *
  rigidMap :: (Element f -> Element f) -> f -> f

En ce qui concerne la cartographie paramétrique, il y a plusieurs façons de le faire. Le moyen le plus simple serait de conserver le courant Functor tel quel. Ensemble, ces classes couvrent des structures comme ByteString, [], Seq, et ainsi de suite. Cependant, ils tombent tous sur Set et Map, à cause de la contrainte Ord sur les valeurs. Heureusement, l'extension constraint kinds entrant dans GHC 7.4 nous permet de résoudre ce problème:

class RFunctor f where
  type Element f a :: Constraint
  type Element f a = ()  -- default empty constraint
  fmap :: (Element f a, Element f b) => (a -> b) -> f a -> f b

Ici, nous disons que chaque instance devrait avoir une contrainte typeclass associée . Par exemple, L'instance Set aura Element Set a = Ord a, pour indiquer que Sets ne peut être construit que si une instance Ord est disponible pour le type. Tout ce qui peut apparaître sur la main gauche de => est acceptée. Nous pouvons définir nos instances précédentes exactement comme elles étaient, mais nous pouvons aussi faire Set et Map:

instance RFunctor Set where
  type Element Set a = Ord a
  fmap = Set.map

instance RFunctor Map where
  type Element Map a = Ord a
  fmap = Map.map

Cependant, il est assez ennuyeux d'avoir à utiliser deux interfaces distinctes pour le mappage rigide et le mappage paramétrique restreint. En fait, ce dernier n'est-il pas une généralisation du premier? Considérez la différence entre Set, qui ne peut contenir que des instances de Ord, et ByteString, qui ne peut contenir que des Word8s. Nous pouvons sûrement exprimer cela comme juste une autre contrainte?

Nous appliquons la même astuce à HasFirst (c'est-à-dire donner des instances pour toute la structure et utiliser une famille de types pour exposer le type d'élément), et introduire une nouvelle famille de contraintes associée:

class Mappable f where
  type Element f :: *
  type Result f a r :: Constraint
  map :: (Result f a r) => (Element f -> a) -> f -> r

L'idée ici est que Result f a r exprime les contraintes dont il a besoin sur le type de valeur (comme Ord a), et aussi contraint le type de conteneur résultant mais il doit le faire; vraisemblablement, pour s'assurer qu'il a le type d'un même type de conteneur de a s. Pour exemple, Result [a] b r sera sans doute besoin que r est [b], et Result ByteString b r exigera que les b est Word8, et r est ByteString.

Les familles de Type nous donnent déjà ce dont nous avons besoin pour exprimer "est" ici: une contrainte d'égalité de type. Nous pouvons dire (a ~ b) => ... pour exiger que a et b soient du même type. Nous pouvons, bien sûr, l'utiliser dans les définitions de famille de contraintes. Donc, nous avons tout ce dont nous avons besoin; sur les instances:

instance Mappable [a] where
  type Element [a] = a
  type Result [a] b r = r ~ [b]
  -- The type in this case works out as:
  --   map :: (r ~ [b]) => (a -> b) -> [a] -> r
  -- which simplifies to:
  --   map :: (a -> b) -> [a] -> [b]
  map = Prelude.map

instance Mappable ByteString where
  type Element ByteString = Word8
  type Result ByteString a r = (a ~ Word8, r ~ ByteString)
  -- The type is:
  --   map :: (b ~ Word8, r ~ ByteString) => (Word8 -> b) -> ByteString -> r
  -- which simplifies to:
  --   map :: (Word8 -> Word8) -> ByteString -> ByteString
  map = ByteString.map

instance (Ord a) => Mappable (Set a) where
  type Element (Set a) = a
  type Result (Set a) b r = (Ord b, r ~ Set b)
  -- The type is:
  --   map :: (Ord a, Ord b, r ~ Set b) => (a -> b) -> Set a -> r
  -- (note the (Ord a) constraint from the instance head)
  -- which simplifies to:
  --   map :: (Ord a, Ord b) => (a -> b) -> Set a -> Set b
  map = Set.map

Parfaite! Nous pouvons définir des instances pour tout type de conteneur que nous voulons, rigide, paramétrique ou paramétrique-mais-restreint, et les types fonctionnent parfaitement.

Disclaimer: Je n'ai pas encore essayé GHC 7.4, donc je ne sais pas si tout cela compile ou fonctionne, mais je pense que les idées de base sont saines.