Haskell subclassing and instance overlap

Question

Coming from the OOP world, I sometimes find myself trying to use the inheritance pattern in Haskell, with varying degrees of success. Here's a little puzzle I encountered with subclassing (using GHC 8.10.7).


{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE UndecidableInstances #-}

import Data.List (sort)

class Collection c a where
    -- gets list of elements in the collection
    elements :: c a -> [a]

class OrderedCollection c a where
    -- gets sorted list of elements in the collection
    orderedElements :: c a -> [a]

instance (Ord a, OrderedCollection c a) => Collection c a where
    -- "default" implementation
    elements = orderedElements

newtype SortedList a = SortedList [a]
    deriving Show

instance (Ord a) => OrderedCollection SortedList a where
    -- need to sort the elements in the list
    orderedElements (SortedList xs) = sort xs

instance Collection SortedList a where
    -- "optimized" implementation: no need to sort
    elements (SortedList xs) = xs

test :: (Ord a, Show a, OrderedCollection c a) => c a -> IO ()
test coll = do
    putStrLn $ "ordered elements: " ++ show (orderedElements coll)
    putStrLn $ "elements:         " ++ show (elements coll)

myList :: SortedList Int
myList = SortedList [3, 2, 1]

main :: IO ()
main = do
    test myList

After including the necessary language extensions, this still gave me an error: Overlapping instances for Collection c a arising from a use of ‘elements’. It suggests using IncoherentInstances. Since this extension is now deprecated in favor of per-instance pragmas, I added an INCOHERENT pragma to the subclass instance:

instance {-# INCOHERENT #-} (Ord a, OrderedCollection c a) => Collection c a where
...

This successfully compiled. However, the result was not what I expected, as the output was:

ordered elements: [1,2,3]
elements:         [1,2,3]

What I wanted was for the specialized implementation of Collection for SortedList to override the default (in an OO language, SortedList would inherit from OrderedCollection and then override the elements method). But here the type checker does not know to use SortedList's custom Collection implementation, because the type signature of test only imposes the constraint OrderedCollection c a.

Next, I tried adding the Collection constraint:

test :: (Ord a, Show a, Collection c a, OrderedCollection c a) => c a -> IO ()

This gave me the output I wanted:

ordered elements: [1,2,3]
elements:         [3,2,1]

However, GHC also issued a warning about "fragile inner bindings" and suggested I add the MonoLocalBinds extension, which silences that warning. In any case, I'm not thrilled with having to include the Collection c a constraint (given it's implied by OrderedCollection c a), or having to use incoherent instances.

Interestingly, if I changed the INCOHERENT pragma to OVERLAPPABLE, it still compiled, and it also allowed me to remove MonoLocalBinds.

My question is, are there any alternative approaches to achieving the desired "inheritance" behavior here, without needing the redundant constraint in test?

user_180286 · Answer

When you write this:

instance ... => Collection c a where

You're declaring a Collection instance for all types ever. And it doesn't matter at all what's on the left of the fat arrow =>. Constraints do not participate in instance resolution. When the compiler tries to lookup an instance for a particular type, it only looks at what's on the right of the fat arrow =>, and only after finding a matching instance does it check if its constraints are satisfied. And if they're not, the compiler won't go back to look for another instance. That's how instance resolution works, and there are good reasons for it.

So, to reiterate: Collection c a means that this is an instance for all types.

And therefore, any subsequent Collection instances you might declare would of course be overlapping.

Thankfully, in this particular case, there is a better way: you can declare default methods without creating a universal instance like that. To do that, declare the method right inside the class declaration. And yes, you can put constraints on it too (see docs):

class Collection c a where
    -- gets list of elements in the collection
    elements :: c a -> [a]
    default elements :: OrderedCollection c a => c a -> [a]
    elements = orderedElements

But more generally, while type classes plus existential quantification is technically equivalent to OOP-style class hierarchies, if you try to actually model your domain like that, it would be more and more awkward and painful the further you go. It's a bit like trying to model ADTs in something like Java. Technically possible, but oh so messy!

There are some legitimate cases where a class hierarchy may make sense (one notable example is the GHC exception system), but most of the time there are much simpler ways.

Haskell subclassing and instance overlap

1 Answers