Comment puis-je préciser que la navette deux opérations dans une classe de types?

Question

Je commencé à lire cet article sur CRDTs , ce qui est une façon de partager des données modifiables en même temps en veillant à ce que les opérations qui modifient les données sont commutative. Il me semblait que ce serait un bon candidat pour l'abstraction dans Haskell -. Fournir une classe de types pour CRDTs qui spécifie un type de données et les opérations qui commutent sur ce type, puis le travail à rendre la bibliothèque pour partager réellement les mises à jour entre les processus simultanés

Ce que je ne peux pas comprendre est comment formuler le contrat que les opérations doivent commuer dans la spécification de la classe de types.

Pour un exemple simple:

class Direction a where
  turnLeft :: a -> a
  turnRight :: a -> a

Il n'y a aucune garantie que turnLeft . turnRight est le même que turnRight . turnLeft. Je suppose que le repli est de préciser l'équivalent des lois monade -. Utiliser un commentaire pour spécifier des contraintes qui ne sont pas appliquées par le système de type

Answer 1

Qu'est-ce que vous voulez est une classe de type qui comprend un fardeau de preuve, quelque chose comme ci-dessous pseudo-Haskell:

class Direction a where
    turnLeft  :: a -> a
    turnRight :: a -> a
    proofburden (forall a. turnLeft (turnRight a) === turnRight (turnLeft a))

Ici, toutes les instances doit fournir à la fois les fonctions et la preuve (s) pour le compilateur de contrôle de type. C'est un vœu pieux (pour Haskell) que Haskell n'a pas (bien limitée) notion de preuve.

OTOH, Coq est un assistant de preuve d'un langage typé dépendamment qui peut extraire de Haskell. Bien que je ne l'ai jamais utilisé Coq avant, une recherche rapide est fructueuse, avec l'exemple:

Class EqDec (A : Type) := {
   eqb : A -> A -> bool ;
   eqb_leibniz : forall x y, eqb x y = true -> x = y }.

Il semble donc que des langues avancées peut le faire, mais il y a sans doute beaucoup de travail à faire pour abaisser la courbe d'apprentissage pour votre développeur standard.

Answer 2

Suite à la réponse de TomMD, vous pouvez utiliser Agda dans le même sens. Bien qu'il ne dispose pas de classes de types, vous obtenez la plupart des fonctionnalités (en dehors de l'envoi dynamique) des dossiers.

record Direction (a : Set) : Set₁ where
  field
    turnLeft  : a → a
    turnRight : a → a
    commLaw   : ∀ x → turnLeft (turnRight x) ≡ turnRight (turnLeft x)

---

Je pensais modifier le message et répondre à la question de savoir pourquoi vous ne pouvez pas le faire en Haskell.

Dans Haskell (+ extensions), vous pouvez représenter l'équivalence tel qu'il est utilisé dans le code Agda ci-dessus.

{-# LANGUAGE GADTs, KindSignatures, TypeOperators #-}

data (:=:) a :: * -> * where
  Refl :: a :=: a  

Cela représente théorèmes sur deux types étant égales par ailleurs. Par exemple. a est équivalente à b est a :=: b.

Où nous ils sont équivalents, nous pouvons utiliser le constructeur Refl. Avec cela, nous pouvons exécuter des fonctions sur les preuves (valeurs) des théorèmes (types).

-- symmetry
sym :: a :=: b -> b :=: a
sym Refl = Refl

-- transitivity
trans :: a :=: b -> b :=: c -> a :=: c
trans Refl Refl = Refl

Ce sont tous de type correct, et donc vrai. Cependant, cela;

wrong :: a :=: b
wrong = Refl

est manifestement erronée et ne parvient pas en effet sur le contrôle de type.

Cependant, à travers tout cela, la barrière entre les valeurs et types n'a pas été rompu. Les valeurs, fonctions de niveau de valeur et des preuves encore vivants sur un côté du côlon; types, fonctions de niveau type et théorèmes vivent de l'autre. Votre turnLeft et turnRight sont des fonctions de niveau de valeur et ne peuvent donc pas être impliqués dans théorèmes.

Agda et Strathclyde Haskell Amélioration (SHE) est un préprocesseur pour le code Haskell qui peut tromper certains des effets du DTP dans Haskell. Elle le fait en dupliquant les données du monde de valeur dans le monde du type. Je ne pense pas qu'il gère dédoubler les fonctions de niveau de valeur encore et si elle l'a fait, mon intuition est que cela pourrait être trop compliqué pour qu'il puisse traiter.

Answer 3

Comme on l'a dit déjà, il n'y a pas moyen de faire respecter ce directement dans Haskell en utilisant le système de type. Mais si simplement spécifier des contraintes dans les commentaires ne sont pas assez satisfaisant, comme un moyen terme que vous pourriez fournir des tests QuickCheck pour les propriétés algébriques souhaitées.

Quelque chose le long de ces lignes se trouve déjà dans la section pions paquet ; vous pouvez le consulter pour l'inspiration.

Answer 4

  

Ce que je ne peux pas comprendre est comment formuler le contrat que les opérations doivent commuer dans la spécification de la classe de types.

La raison pour laquelle vous ne pouvez pas le comprendre est qu'il est impossible. Vous ne pouvez pas encoder ce type de propriété dans les types -. Pas dans Haskell au moins