Can orphan instances cause bugs?

Learn
1

The topic of orphan instances came up again recently.

The usual complaint against orphan instances seems to be that they break the global uniqueness property of type class instances:

Global Uniqueness Property. A type may not be declared as an instance of a particular class more than once in the program.
~ Scott Kilpatrick, A Non-reformist Reform for Haskell Modularity, Section 4.2.1

It seems to me, however, that a weaker version of this property is enforced by GHC today:

Weak Global Uniqueness Property. A type may not be used as an instance of a particular class if it is declared as an instance of that class more than once in the program.

It seems that this is enough to prevent actual bugs in the most common cases. A simple example of orphans potentially causing bad behavior is if you define two sets with different ordering:

module Top where
newtype Foo = Foo Int deriving Eq

module L where
import Top
import Data.Set (fromList)
deriving via Int instance Ord Foo
set1 = fromList (map Foo [1,3..5])

module R where
import Top
import Data.Ord
import Data.Set (fromList)
deriving via Down Int instance Ord Foo
set2 = fromList (map Foo [0,2..4])

module Bot where
import Top
import L
import R
-- bot = set1 <> set2

In the module Bot we have set1 and set2 which are both Set Foo, but with a different internal ordering. It would be a bug to take the union of these two sets with an algorithm that depends on both sets having the same ordering. Luckily, GHC enforces the weak global uniqueness property and does not allow you to use the Ord Foo instance in the Bot module, since there are two such instances in the program. Uncommenting the line will cause a compile-time error, rather than a run-time bug.

Is this weak global uniqueness property is enough to prevent all correctness bugs? Is the only issue with orphan instances that they may become useless if they conflict?

2 Likes
2

No, that is not enough. If you modify it like this, it compiles.

module R where
...
set2 = fromList (map Foo [0,2..4])

combine :: Set Foo -> Set Foo
combine set1 = union set1 set2

module Bot where
...
bot = combine set1 set2
4 Likes
3

Thanks, that makes sense!

Now I also came up with an example that doesn’t require orphans (only FlexibleInstances):

module Top where

data Fun a b = Fun Int (a -> b)
instance Show (Fun a b) where
    show (Fun x _) = show x

module L where

import Top
import Data.Set (Set, fromList)

data Void

instance Eq (Fun Void a) where
    Fun x _ == Fun y _ = x == y
instance Ord (Fun Void a) where
    compare (Fun x _) (Fun y _) = compare x y

set1 :: Set (Fun Void a)
set1 = fromList [Fun i (\x -> case x of {}) | i <- [1,3..5]]

combine :: Set (Fun Void a) -> Set (Fun Void a) -> Set (Fun Void a)
combine = (<>)

module R where

import Top
import Data.Ord
import Data.Set

data Unit = Unit

instance Eq (Fun a Unit) where
    Fun x _ == Fun y _ = x == y
instance Ord (Fun a Unit) where
    compare (Fun x _) (Fun y _) = compare (Down x) (Down y)

set2 :: Set (Fun a Unit)
set2 = fromList [Fun i (\_ -> Unit) | i <- [0,2..4]]

module Main where

import L
import R

main :: IO ()
main = print (combine set1 set2)

That will print:

fromList [1,4,2,0,3,5]
4

Well, that is only true because -Worphans’s definiton of “orphan instances” is a bit too weak. In Rust, those instances would both be considered orphans (because Fun Void a would not be considered a “local type”)

2 Likes
5

Ah, and I guess the Figure 4.2 in section 4.2.3 of Scott Kilpatrick’s thesis has “uncovered” type variables and is therefore rejected by Rust.