Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Fun with types! Resolving multiple instance declarations

I'm trying to write some Haskell code in which there are multiple data types, each of which can have multiple implementations. To do this, I define each data type as a class whose methods are the relevant constructors and selectors, and then implement all operations on members of that class in terms of the given constructors and selectors.

For example, perhaps A is a polynomial class (with methods getCoefficients and makePolynomial) which can have a representation as a SparsePoly or a DensePoly and B is a complex number class (with methods getReal, getImag and makeComplex) which can be represented as a ComplexCartesian or a ComplexPolar.

I've reproduced a minimal example below. I have two classes A and B each of which has an implementation. I want to make all instances of both classes into instances of Num automatically (this requires the FlexibleInstances and UndecidableInstances type extensions). This works fine when I only have one of A or B, but when I try to compile with both, I get the following error:

Duplicate instance declarations:
  instance [overlap ok] (A a, Num x, Show (a x), Eq (a x)) =>
                        Num (a x)
    -- Defined at test.hs:13:10-56
  instance [overlap ok] (B b, Num x, Show (b x), Eq (b x)) =>
                        Num (b x)
    -- Defined at test.hs:27:10-56

I suppose that the 'duplicate instance declarations' message is because a data type could be made an instance of both A and B. I want to be able to make a promise to the compiler that I won't do that, or possibly specify a default class to use in the case that a type is an instance of both classes.

Is there a way to do this (maybe another type extension?) or is this something I'm stuck with?

Here's my code:

{-# LANGUAGE FlexibleInstances, UndecidableInstances, OverlappingInstances #-}

class A a where
    fa :: a x -> x
    ga :: x -> a x

data AImpl x = AImpl x deriving (Eq,Show)

instance A AImpl where
    fa (AImpl x) = x
    ga x = AImpl x

instance (A a, Num x, Show (a x), Eq (a x)) => Num (a x) where
    a1 + a2 = ga (fa a1 + fa a2)
    -- other implementations go here


class B b where
    fb :: b x -> x
    gb :: x -> b x

data BImpl x = BImpl x deriving (Eq,Show)

instance B BImpl where
    fb (BImpl x) = x
    gb x = BImpl x

instance (B b, Num x, Show (b x), Eq (b x)) => Num (b x) where
    -- implementations go here

Edit: To make myself clear, I'm not trying to write any practical code using this technique. I'm doing it as an exercise to help myself understand the type system and extensions better.

like image 528
Chris Taylor Avatar asked Apr 04 '12 16:04

Chris Taylor


1 Answers

This part of your question

I suppose that the 'duplicate instance declarations' message is because a data type could be made an instance of both A and B. I want to be able to make a promise to the compiler that I won't do that, or possibly specify a default class to use in the case that a type is an instance of both classes.

is incorrect. It's actually because you've written two instances,

instance Num (a x)
instance Num (b x)

that the compiler can't tell apart (see the link from @hammar's comment, class contexts don't count for the purpose of differentiating between instance declarations).

One solution is to add a witness type.

{-# LANGUAGE FlexibleInstances, FlexibleContexts, UndecidableInstances, OverlappingInstances #-}

data AWitness

data AImpl witness x = AImpl x deriving (Eq,Show)

instance A (AImpl AWitness) where
    fa (AImpl x) = x
    ga x = AImpl x

instance (A (a AWitness), Num x, Show (a AWitness x), Eq (a AWitness x)) => Num (a AWitness x) where
    a1 + a2 = ga (fa a1 + fa a2)

The compiler can use the witness types to differentiate between your instance declarations.

like image 126
John L Avatar answered Sep 27 '22 17:09

John L