What laws are the standard Haskell type classes expected to uphold?
It's well-known that Monad instances ought to follow the Monad laws. It's perhaps less well-known that Functor instances ought to follow the Functor laws. Nevertheless, I would feel fairly confident writing a GHC rewrite rule that optimizes fmap id == id .
What other standard classes have implicit laws? Does (==) have to be a true equivalence relation? Does Ord have to form a partial order? A total order? Can we at least assume it's transitive? Anti-symmetric?
These last few don't appear to be specified in the Haskell 2010 report nor would I feel confident writing rewrite rules taking advantage of them. Are there any common libraries which do, however? How pathological an instance can one write confidently?
Finally, assuming that there is a boundary for how pathological such an instance can be is there a standard, comprehensive resource for the laws that each type class instance must uphold?
As an example, how much trouble would I be in to define
newtype Doh = Doh Bool
instance Eq Doh where a == (Doh b) = b
is it merely hard to understand or will the compiler optimize incorrectly anywhere?
The Haskell report mentions laws for:
fmap id == id ) m >>= return == m ) (x 'quot' y)*y + (x 'rem' y) == x ) abs x * signum x == x ) showsPrec dxr ++ s == showsPrec dx (r ++ s) ) inRange (l,u) i == elem i (range (l,u)) ) That is all I could find. Specifically, the section about Eq (6.3.1) mentions no laws, neither does the next one about Ord.
My own view of what the laws "ought to be" is not upheld by all standard instances, but I think
Eq should be an equivalence relation. Ord should be a total order Num should be a ring, with fromInteger a ring homomorphism, and abs / signum behaving in the obvious ways. Much code will assume these "laws" to hold even though they don't. This is not a Haskell specific problem, early C allowed compiler to reorder arithmetic according to algebraic laws, and most compilers have an option to do reenable such optimization even though they are not permitted by the current standard and may change your programs results.
It used to be that breaking the Ix laws would let you do just about anything. These days I think they've fixed that. More info here: Does anyone know (or remember) how breaking class laws could cause problems in GHC?
链接地址: http://www.djcxy.com/p/43328.html上一篇: 集合，函数和Eq混淆