Puis-je contraindre une famille de types?

Question

Dans cette récente réponse de la mienne, il m'est arrivé d'en casser ce vieux châtaignier (un programme si vieux, la moitié de ce qui était écrit dans le dix-septième siècle par Leibniz et écrit sur un ordinateur dans les années soixante par mon papa). Je vais laisser le moderne à économiser de l'espace.

class Differentiable f where
  type D f :: * -> *

newtype K a     x  = K a
newtype I       x  = I x
data (f :+: g)  x  = L (f x)
                   | R (g x)
data (f :*: g)  x  = f x :&: g x

instance Differentiable (K a) where
  type D (K a) = K Void
instance Differentiable I where
  type D I = K ()
instance (Differentiable f, Differentiable g) => Differentiable (f :+: g) where
  type D (f :+: g) = D f :+: D g
instance (Differentiable f, Differentiable g) => Differentiable (f :*: g) where
  type D (f :*: g) = (D f :*: g) :+: (f :*: D g)

Maintenant, voici la chose frustrante. Je ne sais pas comment faire pour prévoir qu' D f doit lui-même être dérivable. Certes, ces instances à l'égard de cette propriété, et il peut très bien être amusant de programmes que vous pouvez écrire, qui font usage de la possibilité de garder la différentiation d'un foncteur, prise de vue trous de plus en plus: Taylor expansions, ce genre de chose.

Je voudrais être en mesure de dire quelque chose comme

class Differentiable f where
  type D f
  instance Differentiable (D f)

et exigent un contrôle de cette instance déclarations ont type définitions pour qui le nécessaire instances existent.

Peut-être plus terre à terre des trucs comme

class SortContainer c where
  type WhatsIn c
  instance Ord (WhatsIn c)
  ...

serait aussi agréable. Qui, bien sûr, a la fundep solution de contournement

class Ord w => SortContainer c w | c -> w where ...

mais pour tenter le même truc pour Differentiable semble... bien... compliquée.

Alors, est-il une chouette solution de contournement qui me fait reproductible différentiabilité? (Je suppose que je pourrais construire une représentation GADT et et et... mais est-il une manière qui fonctionne avec des classes?)

Et il y a de toute évidence des chicots avec la suggestion que nous devrions être en mesure de l'insuffisance de la demande sur le type (et, je suppose, de données) des familles lors de la déclaration d'eux, puis vérifiez que les instances les satisfaire?

Answer 1

Certes, la chose la plus évidente serait d'écrire tout simplement souhaité contrainte directement:

class (Differentiable (D f)) => Differentiable (f :: * -> *) where

Hélas, GHC obtient vexée, et refuse de jouer le jeu:

ConstrainTF.hs:17:1:
    Cycle in class declaration (via superclasses):
      Differentiable -> Differentiable
    In the class declaration for `Differentiable'

Donc, comme c'est souvent le cas lors de la tentative de décrire les contraintes de type envie de quitter GHC récalcitrants, nous devons recourir à une certaine manière de la ruse sournoise.

Rappeler un certain nombre de caractéristiques pertinentes de GHC où le type hackery est en cause:

• Il est paranoïaque à ce sujet au niveau du type nontermination loin hors de proportion avec le réel inconvénient que cela implique pour l'utilisateur.
• Il joyeusement en s'engager lui-même des décisions sur les classes et les instances avant il a pris en considération toutes les informations disponibles.
• Il consciencieusement tenter de vérifier ce que vous avez trompé en s'engageant à.

Ce sont des principes qui sous-tendent le familier vieux faux-générique des situations où les types sont unifiés post-hoc avec (~) afin d'améliorer le type d'inférence du comportement de certains type de hackery constructions.

Dans ce cas, cependant, plutôt que de se faufiler type de renseignements passé de GHC, nous devons en quelque sorte empêcher de GHC de remarquer une contrainte de classe, qui est une différente sorte de... heeeey, waaaitaminute....

import GHC.Prim

type family DiffConstraint (f :: * -> *) :: Constraint
type instance DiffConstraint f = Differentiable f

class (DiffConstraint (D f)) => Differentiable (f :: * -> *) where
  type D f :: * -> *

Palan par son propre pétard!

C'est la vraie affaire, trop. Ceux-ci sont acceptés, comme vous en avez l'espoir:

instance Differentiable (K a) where
  type D (K a) = K Void
instance Differentiable I where
  type D I = K ()

Mais si nous l'offrons des bêtises à la place:

instance Differentiable I where
  type D I = []

GHC nous présente précisément le message d'erreur que nous aimerions voir:

ConstrainTF.hs:29:10:
    No instance for (Differentiable [])
      arising from the superclasses of an instance declaration
    Possible fix: add an instance declaration for (Differentiable [])
    In the instance declaration for `Differentiable I'

Il y a un petit hic, bien sûr, à savoir que ce:

instance (Differentiable f, Differentiable g) => Differentiable (f :+: g) where
  type D (f :+: g) = D f :+: D g

...s'avère être moins que le bien-fondé, comme nous l'avons dit, le GHC pour vérifier que, chaque fois qu' (f :+: g) est Differentiable, ainsi en est - (D f :+: D g), qui ne se termine pas bien (ou pas du tout).

La meilleure façon d'éviter cela est, en général, passe-partout sur une pile explicite de la base de cas, mais ici, GHC semble l'intention des divergences de tout temps un Differentiable contrainte s'affiche dans une instance de contexte. Je suppose que c'est inutilement désireux de vérification de l'instance de contraintes en quelque sorte, et pourrait peut-être se laisser distraire assez longtemps avec une autre couche de la ruse, mais je ne suis pas immédiatement savoir par où commencer et avoir épuisé mes capacités pour l'après-minuit type hackery ce soir.

---

Un peu de discussion IRC sur #haskell réussi à jogging ma mémoire un peu sur la façon dont GHC poignées de classe contexte de contraintes, et il semble que nous pouvons patch les choses un petit peu par le biais d'une contrainte de plus en plus pointilleuses de la famille. En utilisant ceci:

type family DiffConstraint (f :: * -> *) :: Constraint
type instance DiffConstraint (K a) = Differentiable (K a)
type instance DiffConstraint I = Differentiable I
type instance DiffConstraint (f :+: g) = (Differentiable f, Differentiable g)

Nous avons maintenant beaucoup plus sage de récursivité pour les sommes:

instance (Differentiable (D f), Differentiable (D g)) => Differentiable (f :+: g) where
  type D (f :+: g) = D f :+: D g

Le récursive cas ne peut pas être si facilement coupée en deux pour les produits, cependant, et en appliquant les mêmes changements, il n'y amélioré que dans la mesure où j'ai reçu un contexte de réduction de débordement de pile plutôt que de simplement flâner dans une boucle infinie.

Answer 2

Votre meilleur pari pourrait être de définir quelque chose en utilisant le paquet constraints :

 import Data.Constraint

class Differentiable (f :: * -> *) where
  type D f :: * -> *
  witness :: p f -> Dict (Differentiable (D f))
 

alors vous pouvez ouvrir manuellement le dictionnaire chaque fois que vous avez besoin de recurse.

Cela vous permettrait d'utiliser la forme générale de la solution dans la réponse de Casey, sans que le compilateur (ou le moteur d'exécution) ne tourne à l'infini sur l'induction.

Answer 3

Ceci peut être accompli de la même manière que Edward suggère avec une petite mise en œuvre de l' Dict. Tout d'abord, commençons par les extensions de langage et les importations de la route.

{-# LANGUAGE TypeOperators #-}
{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE ConstraintKinds #-}
{-# LANGUAGE GADTs #-}
{-# LANGUAGE RankNTypes #-}

import Data.Proxy

TypeOperators est uniquement pour votre exemple de problème.

Minuscule Dict

Nous pouvons faire de notre petite mise en œuvre de l' Dict. Dict utilise un GADT et ConstraintKinds de la capture de toute contrainte dans le constructeur pour un GADT.

data Dict c where
    Dict :: c => Dict c  

withDict et withDict2 réintroduire la contrainte par pattern matching sur le GADT. Nous avons seulement besoin d'être capable de raisonner sur les conditions d'un ou de deux sources de contraintes.

withDict :: Dict c -> (c => x) -> x
withDict Dict x = x

withDict2 :: Dict a -> Dict b -> ((a, b) => x) -> x
withDict2 Dict Dict x = x

Infiniment dérivable types

Maintenant, nous pouvons parler infiniment dérivable types, dont les dérivés doivent également être dérivable

class Differentiable f where
    type D f :: * -> *
    d2 :: p f -> Dict (Differentiable (D f))
    -- This is just something to recover from the dictionary
    make :: a -> f a

d2 prend un proxy pour le type, et récupère le dictionnaire pour la prise de la dérivée seconde. Le proxy permet de facilement spécifier le type de l' d2 nous parlons. Nous pouvons obtenir plus de dictionnaires en appliquant d:

d :: Dict (Differentiable t) -> Dict (Differentiable (D t))
d d1 = withDict d1 (d2 (pt (d1)))
    where
        pt :: Dict (Differentiable t) -> Proxy t
        pt = const Proxy

La capture de la dictonary

Le polynôme foncteur types de produits, des sommes, des constantes, et zéro, sont tous infiniment dérivable. Nous allons définir l' d2 des témoins pour chacun de ces types

data    K       x  = K              deriving (Show)
newtype I       x  = I x            deriving (Show)
data (f :+: g)  x  = L (f x)
                   | R (g x)
                                    deriving (Show)
data (f :*: g)  x  = f x :&: g x    deriving (Show)

Zéro et constantes ne nécessite pas de connaissance supplémentaire pour capturer leurs dérivés Dict

instance Differentiable K where
  type D K = K
  make = const K
  d2 = const Dict

instance Differentiable I where
  type D I = K
  make = I
  d2 = const Dict

Somme et produit tous les deux exigent de dictionnaires à partir de deux de leurs produits dérivés pour être en mesure de déduire le dictionnaire pour leurs dérivés.

instance (Differentiable f, Differentiable g) => Differentiable (f :+: g) where
  type D (f :+: g) = D f :+: D g
  make = R . make
  d2 p = withDict2 df dg $ Dict
    where
        df = d2 . pf $ p
        dg = d2 . pg $ p
        pf :: p (f :+: g) -> Proxy f
        pf = const Proxy
        pg :: p (f :+: g) -> Proxy g
        pg = const Proxy

instance (Differentiable f, Differentiable g) => Differentiable (f :*: g) where
  type D (f :*: g) = (D f :*: g) :+: (f :*: D g)
  make x = make x :&: make x
  d2 p = withDict2 df dg $ Dict
    where
        df = d2 . pf $ p
        dg = d2 . pg $ p
        pf :: p (f :*: g) -> Proxy f
        pf = const Proxy
        pg :: p (f :*: g) -> Proxy g
        pg = const Proxy

Récupérer le dictionnaire

Nous pouvons récupérer le dictionnaire des contraintes que nous n'avons pas suffisamment d'informations pour en déduire. Differentiable f ne devrait normalement laisser utiliser get pour make :: a -> f a, mais pas ou make :: a -> D f a ou make :: a -> D (D f) a.

make1 :: Differentiable f => p f -> a -> D f a
make1 p = withDict (d2 p) make

make2 :: Differentiable f => p f -> a -> D (D f) a
make2 p = withDict (d (d2 p)) make