CODEWITHSUNDEEP
haskelltypeclass
CowNorris
CowNorris

Reputation: 432

Typeclass projections as inheritance

I want to allow typeclasses to be easily "inherited" on union types, by deriving the typeclass automatically when there exists a projection (this projection is another typeclass that I defined separately). Below is some code illustrating what I'm trying to achieve:

class t ##-> a where -- the projection
    inj :: t -> a
    prj :: a -> Maybe t
class Prop t where -- the property
    fn1 :: Int -> t
    fn2 :: t -> t
instance (t #-> a, Prop t) => Prop a where -- deriving the property from the projection
    cst :: Int -> a
    cst = inj . fn1 @t
    fn2 :: a -> a
    fn2 a1 = inj $ fn2 @t $ fromJust (prj a1)

And so, when I define a sum type, I can define only the projection #->, without redefining the typeclass Prop on the sum type.

data K = ...
instance Prop K
data SumType = E1 K | ...
instance K #-> SumType where
    inj :: K -> SumType 
    inj = E1
    prj :: SumType -> Maybe K
    prj (E1 k) = Just k
    prj _ = Nothing

However, I ran into the following problem, when I would like to reuse typeclass functions in the instance definition. For example, when I am trying to give a Prop class definition for a base type (say, String):

instance Prop String where
    cst :: Int -> String
    cst = show
    fn2 :: String -> String
    fn2 s = if s == cst 0 then "0" else s -- Overlapping instances for Prop String arising from a use of ‘cst’

The compiler isn't sure whether to use the derived type (from the #-> derivation), or to use the base instance I defined (i.e. the Prop String definition). It seems obvious to me however, that in the Prop String definition, the cst @String definition should be used. Using {-# LANGUAGE TypeApplications #-} also does not seem to help the compiler determine the instance needed.

I'm wondering how would we go about convincing the compiler to use the instance I intended here?

Upvotes: 0

Views: 76

Answers (1)

Silvio Mayolo
Silvio Mayolo

Reputation: 70267

Generally speaking, when Haskell looks for instances and you've written instance (Context) => Head, Haskell only sees Head. It's a long-running technical thing, and it's designed that way for a variety of reasons. What that means for you is: Haskell pattern-matches only on the Head part, and then uses the Context to determine if it should proceed or issue an error. It will not backtrack and look for another Head if the Context fails.

instance (t #-> a, Prop t) => Prop a

So what you're saying here is incredibly strong. You're saying that if anyone ever calls fn1 or fn2 on any type a, this one instance right here is the canonical place to look. Either this canonical instance will work (if t #-> a and Prop t), or nothing will. Which is obviously not what you mean.

I don't have a way to get what you want. It's possible in Scala, but that's because Scala's implicit resolution engine is willing to backtrack where Haskell's isn't. Here's what I would recommend as idiomatic in Haskell.

Step 1: Declare a functional dependency on ##->.

class t ##-> a | a -> t where -- the projection
    inj :: t -> a
    prj :: a -> Maybe t

This is necessary since, given a Prop a instance, we need to know which t to look for. If you can't guarantee that a (the larger type) uniquely determines t (the smaller type), then you won't be able to do this, since type inference can't figure out which t you want.

Step 2: Provide a default implementation if your conditions are satisfied.

{-# LANGUAGE DefaultSignatures #-}

class Prop a where
    fn1 :: a -> a
    default fn1 :: (Prop t, t ##-> a) -> a -> a
    fn1 = undefined -- Your implementation if (Prop t, t ##-> a) here.

Step 3: When Prop t and t ##-> a are both true, implementors can simply write

instance Prop a

and their code will happily adopt the default fn1 instance.

It's not quite what you were asking for, and it does require implementors to write a one-line empty instance definition. But, for better or worse, Haskell's type resolution engine is not a full-fledged logic programming language, so we do have to make concessions at times.

Upvotes: 3

Related Questions