Come faccio a specificare che due operazioni di pendolari in un typeclass?

Question

Ho iniziato a leggere questa carta su CRDTs , che è un modo di scambio dati modificabili contemporaneamente da garantire che le operazioni che modificano i dati sono commutative. Mi sembrava che questo sarebbe un buon candidato per l'astrazione in Haskell -. Fornire un typeclass per CRDTs che specifica un tipo di dati e le operazioni che i pendolari su quel tipo, allora il lavoro per rendere biblioteca realmente condividono gli aggiornamenti tra processi concorrenti

Quello che non riesco a capire è come frase del contratto che le operazioni devono commutare nella specifica del typeclass.

Per un semplice esempio:

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

Non c'è alcuna garanzia che turnLeft . turnRight è lo stesso di turnRight . turnLeft. Suppongo che il ripiego è quello di specificare l'equivalente delle leggi monade -. Utilizzare un commento per specificare vincoli che non vengono applicate dal sistema di tipo

Answer 1

Ciò che si vuole è una classe tipo che include un onere della prova, qualcosa di simile al di sotto pseudo-Haskell:

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

Qui tutto istanza deve fornire entrambe le funzioni e la prova (s) per il compilatore di controllo di tipo. Questo è un pio desiderio (per Haskell) come Haskell non ha (ben limitato,) nozione di prova.

OTOH, Coq è un assistente di prova per un linguaggio dipendente tipizzato che può estrarre a Haskell. Mentre io ho mai usato Coq prima, una rapida ricerca è feconda, con l'esempio:

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

Quindi sembra lingue avanzate possono fare questo, ma non v'è senza dubbio molto lavoro da fare nel ridurre la curva di apprendimento per il vostro sviluppatore standard.

Answer 2

A seguito della risposta del TomMD, è possibile utilizzare Agda per lo stesso effetto. Anche se non ha typeclasses, si ottiene la maggior parte delle funzionalità (a parte la spedizione dinamico) da record.

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

---

ho pensato di modificare il post e rispondere alla domanda del perché non si può fare questo in Haskell.

In Haskell (+ estensioni), si può rappresentare equivalenza utilizzata nel codice Agda sopra.

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

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

Questo rappresenta teoremi sui due tipi parità. Per esempio. a equivale a b è a :=: b.

Dove siamo sono equivalenti, si può utilizzare il Refl costruttore. Usando questo, siamo in grado di svolgere funzioni per le prove (valori) dei teoremi (tipi).

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

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

Questi sono tutti di tipo corretto e quindi vero. Tuttavia questo;

wrong :: a :=: b
wrong = Refl

è chiaramente sbagliato e in effetti non del tipo di controllo.

Tuttavia, tutto questo, la barriera tra i valori e tipi non è stato rotto. Valori, funzioni a livello di valore e prove ancora in tensione su un lato del colon; tipi, funzioni di tipo livello e teoremi vivono dall'altra. Il tuo turnLeft e turnRight sono funzioni a livello di valore e quindi non possono essere coinvolti in teoremi.

Agda e Coq sono linguaggi dipendente-digitati, in cui la barriera non esiste o le cose sono autorizzati a attraversare. Strathclyde Haskell Enhancement (SHE) è un preprocessore codice Haskell che può imbrogliare alcuni degli effetti di DTP in Haskell. Lo fa duplicazione di dati dal mondo valore nel mondo tipo. Io non credo che gestisce duplicare funzioni a livello di valore ancora e se lo ha fatto, la mia impressione è che questo potrebbe essere troppo complicato per poter gestire.

Answer 3

Come è stato detto già, non c'è modo di far rispettare questo direttamente in Haskell utilizzando il sistema tipo. Ma se semplicemente specificando i vincoli nei commenti non è abbastanza soddisfacente, come una via di mezzo si potrebbe fornire prove QuickCheck per le proprietà algebriche desiderate.

Qualcosa in questo senso è già presente nel dama pacchetto ; si consiglia di consultare per l'ispirazione.

Answer 4

Quello che non riesco a capire è come frase del contratto che le operazioni devono commutare nella specifica del typeclass.

La ragione che non si può capire è che non è possibile. Non si può codificare questo tipo di proprietà nei tipi -. Non in Haskell almeno