Какие законы должны соблюдать стандартные классы типа Хаскелла?

Хорошо известно, что экземпляры Monad должны следовать законам монады. Возможно, менее известно, что экземпляры Functor должны следовать законам функтора. Тем не менее, я бы чувствовал себя достаточно уверенно, написав правило перезаписи GHC, которое оптимизирует fmap id == id.

Какие еще стандартные классы имеют неявные законы? Должно ли (==) быть истинным отношением эквивалентности? Должен ли Ord образовывать частичный порядок? Полный порядок? Можем ли мы, по крайней мере, предположить, что это транзитивно? Антисимметричный?

Эти последние некоторые из них, по-видимому, не указаны в отчете Haskell 2010, и я бы не чувствовал себя уверенным в написании правил перезаписи, используя их. Однако существуют ли какие-либо общие библиотеки, которые это делают? Насколько патологический пример можно написать уверенно?

Наконец, если предположить, что существует граница для того, насколько патологическим может быть такой экземпляр, существует ли стандартный, всеобъемлющий ресурс для законов, которые должен соблюдать каждый экземпляр класса типа?

В качестве примера, сколько хлопот я бы будьте в том, чтобы определить 

newtype Doh = Doh Bool
instance Eq Doh where a == (Doh b) = b

Это просто трудно понять или компилятор где-то неправильно оптимизирует?

3 9
haskell interface proof

3 ответа:

В докладе Хаскеллаупоминаются законы для:

  • функтор (например, fmap id == id)
  • Монада (например, m >>= return == m)
  • Интеграл (например, (x ‘quot‘ y)*y + (x ‘rem‘ y) == x)
  • Num (abs x * signum x == x)
  • показать (showsPrec d x r ++ s == showsPrec d x (r ++ s))
  • Ix (например, inRange (l,u) i == elem i (range (l,u)))

Это все, что я смог найти. В частности, раздел о EQ (6.3.1) упоминает ни законов, ни не следующий об ОРД.

5

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

  • Eq должно быть отношение эквивалентности.
  • Ord должен быть полный порядок
  • Num должно быть кольцом, с fromInteger кольцевым гомоморфизмом, и abs/signum ведет себя самым очевидным образом.

Большая часть кода будет предполагать, что эти "законы" выполняются, даже если они этого не делают. это не специфическая проблема Хаскелла, ранний C позволил компилятору переупорядочить арифметику в соответствии с алгебраическими законами, и большинство компиляторов имеют возможность сделать повторную такую оптимизацию, даже если они не разрешены текущим стандартом и могут изменить результаты ваших программ.

3

Раньше считалось, что нарушение законов Ix позволит вам делать все, что угодно. В наши дни, я думаю, они это исправили. Более подробная информация здесь: Кто-нибудь знает (или помнит), как нарушение классовых законов может вызвать проблемы в GHC?

1