Какие законы являются стандартными классами классов Haskell, которые должны поддерживаться?

Question

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

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

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

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

---

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

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

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

Answer 1

Haskell report упоминает законы для:

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

Это все, что я мог найти. В частности, в разделе, посвященном Eq (6.3.1), не упоминается никаких законов, а также не о следующем.

Answer 2

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

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

Многозначный код будет принимать эти «законы», даже если они этого не делают. Это не проблема Haskell, ранний C разрешил компилятору переупорядочить арифметику в соответствии с алгебраическими законами, и большинство компиляторов имеют возможность повторно использовать такую ​​оптимизацию, даже если они не разрешены текущим стандартом и могут изменять результаты ваших программ.

Answer 3

Раньше было, что нарушение законов Ix позволило бы вам сделать что угодно. В эти дни я думаю, что они исправили это. Больше информации здесь: Does anyone know (or remember) how breaking class laws could cause problems in GHC?