Optimize Superclass Method Depending on Subclass

Question

Can I provide a refined implementation (aka. override in OOP) of a method in a class instance, when the type is in another class, too? Or at least, if that other class is a subclass.

I have a class C with method m, a subclass S of C with method s and a type T a so there are instantiations

class C a where m :: [a] -> Bool
class C a => S a where s :: a -> a -> Bool
instance C a => C (T a) where m = ...
instance S a => S (T a) where s = ...

as usual. Now it happens to be that when T a is in the subclass (which I cannot know as it depends on a), method m could be implemented much more efficient (quadratic vs. exponential time) using s.

I tried 'overriding' m in the implementation

instance S a => S (T a) where
    s = ...
    m = (all . uncurry) (=^=) . pairs -- override C.m

but the compiler errors basically because, m is not a public method of S. Well, it is not, but it's inherited in the OO sense.

For the specific purpose, the specialized version of m can be used for all instances; it's not a default to be overridden anywhere.

---

Edit: Because requested, the concrete code with a bit of explanation.

I have a class Model which has (among others) a method con that checks a list for consistency.

class Model a where
    con :: [a] -> Bool

Two models can form an arrow model.

data Arrow a b = [a] :->: b
lhs w = [ a | (u :->: _) <- w, a <- u ]
rhs w = [ b | (_ :->: b) <- w ]

For the specific instance Model (Arrow a b), the general con implementation is very expensive (note powerset in the definition).

instance (Model a, Model b) => Model (Arrow a b) where
    con w = all (\w' -> con (lhs w') `implies` con (rhs w')) (powerset w)

There is a subclass CoherentModel of Model which has a method (=^=) that checks consistency for two objects. The condition for coherent models is that a list is consistent iff all pairs are.

class Model a => CoherentModel a where
    (=^=) :: a -> a -> Bool
    a =^= b = con [a, b]

The class CoherentModel is at this point more documentation than a feature.

So, given that a model is coherent, consistency is much more efficient to check.

instance (Model a, CoherentModel b) => CoherentModel (Arrow a b) where
    (u :->: a) =^= (v :->: b) = con (u ++ v) `implies` a =^= b

And in this case, con can be implemented using

con = (all . uncurry) (=^=) . pairs
  where
    pairs :: [a] -> [(a,a)]
    pairs [] = []
    pairs [_] = []
    pairs [x,y] = [(x,y)]
    pairs (x:xs) = map ((,) x) xs ++ pairs xs

but I find no way to specify this. It's not only for Arrow, it's relevant for all models with parameter. I chose Arrow because the improvement is significant.

Answer 1

It's a good question. One thing to remember is that whether a data type is an instance of a typeclass is compile-time only information -- i.e. we are always able to choose which instance to use using statically available information at the use site, and polymorphism comes from being able to choose an instance from the context. In general, if you ask "is a a member of typeclass B?", the only answers you can get are "yes" and "compile error". (This second observation is changed a bit by OverlappingInstances, but it doesn't seem to help in your case)

So the answer to your immediate question is no. You can't make a decision about a type's membership in a type class unless you are a method of that type class. What we can do is add this decision as a method (using the constraints package)

import Data.Constraint

class Model a where
    con :: [a] -> Bool
    isCoherent :: Maybe (Dict (CoherentModel a))
    isCoherent = Nothing

Which you can define trivially for any type you have instantiated CoherentModel at:

instance Model Foo where
    con = ...
    isCoherent = Just Dict

Now you can implement your decision like this (w/ extensions ScopedTypeVariables and TypeApplications):

instance (Model a, Model b) => Model (Arrow a b) where
    con | Just Dict <- isCoherent @b = -- efficient implementation
        | otherwise                  = -- inefficient implementation

In the body of the first case we will have a local CoherentModel b in the context. It's kind of cool.

Too bad we have a sort of expression problem here where all the different implementations of con need to be collected up into one place. Also too bad isCoherent needs to be implemented manually on each coherent Model instance, separate from where its CoherentModel instance is.

There is a lot to explore here but I have to go. Good luck!