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

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

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

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

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

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

Ответ 1

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

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

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

OTOH, Coq - помощник доказательства для строго типизированного языка, который можно извлечь в Haskell. Хотя я никогда не использовал классы классов Coq, быстрый поиск является плодотворным, с примером:

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

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

Ответ 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.

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

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

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

Это означает, что теоремы о двух типах равны. Например. a эквивалентно b is 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 являются функциями уровня ценности и поэтому не могут участвовать в теоремах.

Agda и Coq зависят языками, где барьер не существует или что-то разрешено пересекать. Strathclyde Haskell Enhancement (SHE) является препроцессором для кода Haskell, который может обмануть некоторые эффекты DTP в Haskell. Он делает это путем дублирования данных из мира ценностей в мире типов. Я не думаю, что он обрабатывает дублирование функций уровня ценности еще, и если бы это произошло, моя догадка, это может быть слишком сложно для обработки.

Ответ 3

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

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

Ответ 4

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

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