¿Cómo puedo especificar que conmutan dos operaciones en una clase de tipos?

Question

este documento sobre Crdts , que es una forma de compartir los datos modificables al mismo tiempo, garantizando que las operaciones que modifican los datos son conmutativa. Me parecía que este sería un candidato bueno para la abstracción en Haskell -. Proporcionar una clase de tipos de Crdts que especifica un tipo de datos y las operaciones que se conmutan en ese tipo, entonces el trabajo en la fabricación de la biblioteca para realmente comparten las actualizaciones entre procesos concurrentes

Lo que no puedo entender es cómo expresar el contrato que las operaciones deben viajar en la especificación de la clase de tipos.

Para un simple ejemplo:

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

No hay ninguna garantía de que turnLeft . turnRight es la misma que turnRight . turnLeft. Supongo que el repliegue es especificar el equivalente a las leyes de las mónadas -. Utilizar un comentario para especificar restricciones que no son impuestas por el sistema de tipos

Answer 1

Lo que queremos es una clase de tipo que incluye una carga de prueba, algo así como el siguiente pseudo-Haskell:

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

Aquí todo caso debe proporcionar ambas funciones y la prueba (s) para el compilador de comprobación de tipos. Esto es una ilusión (por Haskell) como Haskell no tiene (bueno, limitado) noción de prueba.

otoh, Coq es un asistente de prueba para un lenguaje dependiente de mecanografiado que se puede extraer a Haskell. Aunque nunca he utilizado Coq antes, una búsqueda rápida es fructífera, con el ejemplo:

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

Así que parece idiomas avanzados puede a hacer esto, pero es sin duda mucho trabajo por hacer en la reducción de la curva de aprendizaje para su desarrollador estándar.

Answer 2

con la respuesta de TomMD, puede utilizar Agda en el mismo sentido. A pesar de que no tiene clases de tipos, se obtiene la mayor parte de la funcionalidad (aparte de envío dinámico) de los registros.

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

---

pensé que editar la entrada y responda a la pregunta de por qué no se puede hacer esto en Haskell.

En Haskell (+ extensiones), que puede representar equivalencia utilizada en el código Agda anteriormente.

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

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

Esto representa teoremas sobre dos tipos son iguales. P.ej. a es equivalente a b se a :=: b.

Cuando nos son equivalentes, podemos utilizar el Refl constructor. Usando esto, podemos realizar funciones en las pruebas (valores) de los teoremas (tipos).

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

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

Estos son todos de tipo correcto, y por lo tanto cierto. Sin embargo esto;

wrong :: a :=: b
wrong = Refl

es claramente equivocado y en efecto, un error en la comprobación de tipos.

Sin embargo, a través de todo esto, la barrera entre los valores y tipos no se ha roto. Los valores, las funciones a nivel de valor y pruebas todavía vivo en un lado del colon; tipos, funciones de nivel tipo y teoremas viven en el otro. Su turnLeft y turnRight son funciones de nivel de valor y por lo tanto no pueden participar en teoremas.

Agda y Coq son lenguajes de tipo dependientemente-, donde la barrera no existe o cosas están autorizados a cruzar. El Strathclyde Haskell Enhancement (SHE) es un preprocesador para el código Haskell que puede engañar a algunos de los efectos de DTP en Haskell. Esto se hace mediante la duplicación de datos del mundo de valor en el mundo tipo. No creo que maneja duplicando funciones a nivel de valor y aún si lo hiciera, mi impresión es que esto podría ser demasiado complicado para que pueda manejar.

Answer 3

As has been stated already, there's no way to enforce this directly in Haskell using the type system. But if merely specifying constraints in comments isn't satisfying enough, as a middle ground you could provide QuickCheck tests for the desired algebraic properties.

Something along these lines can already be found in the checkers package; you may want to consult it for inspiration.

Answer 4

What I can't figure is how to phrase the contract that operations must commute in the specification of the typeclass.

The reason that you can't figure it out is that it's not possible. You can't encode this kind of property in types - not in Haskell at least.