Wie kann ich diese zwei Operationen pendeln in einem typeclass angeben?

Question

begann ich zu lesen dieses Papier auf CRDTs , die eine Art und Weise des Teilens modifizierbaren Daten gleichzeitig, indem sichergestellt wird, dass die Operationen, die die Daten sind kommutativ modifizieren. Es schien mir, dass dies ein guter Kandidat für die Abstraktion in Haskell wäre -. Bietet eine typeclass für CRDTs, die angibt, ein Datentyp und Operationen, die pendeln auf dieser Art, dann die Arbeit an Bibliothek zu machen, um tatsächlich das Updates zwischen gleichzeitigen Prozessen teilen

Was kann ich nicht Figur ist, wie Begriff der Vertrag, dass Operationen in der Spezifikation des typeclass pendeln müssen.

Für ein einfaches Beispiel:

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

Es gibt keine Garantie, dass turnLeft . turnRight die gleichen wie turnRight . turnLeft ist. Ich nehme an, der Rückfall ist das Äquivalent der Monade Gesetze zu geben -. Verwenden, um einen Kommentar Einschränkungen angeben, die vom Typ System nicht erzwungen werden

Answer 1

Was Sie wollen, ist eine Art Klasse, die einen Beweis Belastung, so etwas wie das unten pseudo-Haskell enthält:

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

Hier werden alle Instanz muss beide Funktionen zur Verfügung stellen und den Nachweis (e) für den Compiler Typprüfung. Das ist Wunschdenken (für Haskell) als Haskell keinen (na ja, beschränkt) Begriff des Beweises hat.

OTOH ist Coq ein Beweis Assistent für eine abhängig typisierte Sprache, die Haskell extrahieren kann. Während ich noch nie Coq der Typklassen verwendet haben , eine schnelle Suche ist fruchtbar, mit dem Beispiel:

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

So ist es wie erweiterte Sprachen aussieht können dies tun, aber es ist wohl viel Arbeit bei der Senkung der Lernkurve für Standardentwickler zu tun.

Answer 2

Im Anschluss an TomMD Antwort, können Sie Agda auf den gleichen Effekt verwendet werden. Obwohl es typeclasses nicht haben, erhalten Sie die meisten Funktionen (abgesehen von dynamischen Dispatch) von Aufzeichnungen.

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

---

Ich dachte, ich den Post bearbeiten würde und die Frage beantworten, warum diese in Haskell nicht tun können.

In Haskell (+ Erweiterungen) können Sie Gleichwertigkeit darstellen, wie oben im Agda Code verwendet wird.

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

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

Dies stellt Sätze über zwei Typen gleich sind. Z.B. a entspricht b ist a :=: b.

Wo sind wir, sie sind gleichwertig wir den Konstruktor Refl verwenden können. Mit diesem können wir Funktionen auf den Beweisen (Werte) der Sätze (Typen) durchführen.

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

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

Diese sind alle typ richtig, und deshalb wahr. Doch diese;

wrong :: a :=: b
wrong = Refl

ist eindeutig falsch und in der Tat ist nicht auf Typprüfung.

Doch durch all dies hat die Barriere zwischen den Werten und Typen nicht gebrochen worden. Werte, Wert-Level-Funktionen und Proofs leben noch auf einer Seite des Dickdarms; Typen, Typ-Level-Funktionen und Theoreme leben auf der anderen Seite. Ihre turnLeft und turnRight sind Wert-Level-Funktionen und können daher nicht in Sätzen mit einbezogen werden.

Agda und Strathclyde Haskell Enhancement (SHE) ein Präprozessor für Haskell-Code ist das kann einige der Auswirkungen von DTP in Haskell betrug. Es tut dies, indem Daten aus der Wertewelt in der Art Welt zu duplizieren. Ich glaube nicht, es Wert-Level-Funktionen Griffe Duplizieren noch und wenn es so wäre, meine Vermutung ist, könnte dies zu kompliziert für sie zu handhaben.

Answer 3

Wie bereits erwähnt, gibt es keine Möglichkeit, dies in Haskell mit dem Typ-System direkt zu erzwingen. Aber wenn nur Einschränkungen in den Kommentaren Angabe ist nicht genug erfüllt, als Mittelweg könnten Sie Quick Check-Tests für die gewünschten algebraischen Eigenschaften liefern.

Etwas in dieser Richtung bereits in der Kontrolleure Paket ; Sie kann es für die Inspiration konsultieren wollen.

Answer 4

Was kann ich nicht Figur ist, wie Begriff der Vertrag, dass Operationen in der Spezifikation des typeclass pendeln müssen.

Der Grund, dass Sie es nicht herausfinden können, ist, dass es nicht möglich ist. Sie können nicht diese Art von Eigentum in Typen kodieren -. Nicht in Haskell mindestens