Как я могу указать, что две операции ездят в типовом классе?

Question

Я начал читать Эта статья о CRDTS, который является способом обмена модифицируемыми данными одновременно путем обеспечения коммутативных операций, которые изменяют данные. Мне казалось, что это будет хорошим кандидатом на абстракцию в Хаскелле - предоставить типов для CRDT, которые определяют данные дата и операции, которые едут по этому типу, а затем работают над созданием библиотеки, чтобы фактически обмениваться обновлениями между параллельными процессами.

Я не могу понять, как сформулировать контракт, который операции должны ездить на спецификации типа.

Для простого примера:

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

Нет никакой гарантии, что turnLeft . turnRight такой же как turnRight . turnLeft. Анкет Я полагаю, что запасная сторона состоит в том, чтобы указать эквивалент законов Монады - использовать комментарий, чтобы указать ограничения, которые не применяются в системе типов.

Answer 1

Вам нужен класс типов, который включает в себя нагрузку на доказательство, что-то вроде приведенного ниже псевдо-хаскелла:

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

Здесь все экземпляры должны предоставить как функции, так и доказательства для компилятора для типа проверки. Это желаемое мышление (для Хаскелла), поскольку у Хаскелла нет (ну, ограниченного) понятия доказательства.

OTOH, COQ является ассистентом для зависимого напечатанного языка, который может извлечь в Haskell. Пока я никогда не использовал Классы типа CoQ Раньше быстрый поиск плодотворен, с примером:

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

Так что это похоже на продвинутые языки Можно Сделайте это, но, возможно, есть много работы по снижению кривой обучения для вашего стандартного разработчика.

Answer 2

В дополнение к ответу Tommd, вы можете использовать AGDA к тому же эффекту. Хотя в нем нет типовых классов, вы получаете большую часть функциональности (кроме динамической диспетчеры) от записей.

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

---

Я думал, что отредактирую пост и отвечу на вопрос о том, почему вы не можете сделать это в Хаскелле.

В Haskell (+ расширения) вы можете представлять эквивалентность, используемая в коде AGDA выше.

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

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

Это представляет теоремы о том, что два типа равны. Например a эквивалентно b является a :=: b.

Где мы эквивалентны, мы можем использовать конструктор Refl. Анкет Используя это, мы можем выполнять функции на доказательствах (значения) теорем (типы).

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

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

Все они корректны типа и, следовательно, верны. Однако это;

wrong :: a :=: b
wrong = Refl

явно неправильно и действительно не удается при проверке типов.

Однако, несмотря на все это, барьер между значениями и типами не был нарушен. Значения, функции уровня стоимости и доказательства по-прежнему живут на одной стороне толстой кишки; Типы, функции типа и теоремы живут на другом. Ваш turnLeft а также turnRight являются функциями уровня стоимости и, следовательно, не могут быть вовлечены в теоремы.

Агда а также Кок являются зависимыми языками, где барьер не существует, или вещи могут пересечь. А Усовершенствование Strathclyde Haskell (она) является препроцессором кода Хаскелла, который может обмануть некоторые эффекты DTP в Haskell. Это происходит путем дублирования данных из мира ценностей в мире типов. Я еще не думаю, что это обрабатывает дублирующие функции на уровне ценности, и, если это так, моя догадка в том, что это может быть слишком сложно, чтобы с этим справиться.

Answer 3

Как уже говорилось, нет никакого способа обеспечить соблюдение этого непосредственно в Хаскелле, используя систему типов. Но если просто указание ограничений в комментариях не достаточно удовлетворяет, поскольку средняя земля вы можете провести тесты QuickCheck для желаемых алгебраических свойств.

Что -то в этом направлении уже можно найти в пакет шашек; Вы можете проконсультироваться с этим для вдохновения.

Answer 4

Я не могу понять, как сформулировать контракт, который операции должны ездить на спецификации типа.

Причина, по которой вы не можете понять это, заключается в том, что это невозможно. Вы не можете кодировать такое свойство в типах - по крайней мере, не в Хаскелле.