Haskell "newtype" for type synonyms

Question

I'm doing some stuff with SAT, and I want to have both "and" and "or" clauses.

type AndClause = [Literal]
type OrClause  = [Literal]

But I'm running into problems when I use them:

instance Satisfiable AndClause where ...
instance Satisfiable OrClause where ...

Gives me "Duplicate instance declarations." They are types, not data or type constructors, so I don't think I can use newtype to do what I want. Is there any solution?

Answer 1

The problem is that you seem to want two conflicting things at once:

1. You want different names for the same type
2. You want the compiler to understand those two type names as referring to different types

Based on the domain, I think you certainly don't want to be using type synonyms, and that you do want actual new types (with accompanying type constructors). If AndClause is a synonym for [Literal], and OrClause is a synonym for [Literal], then by the transitive property, AndClause and OrClause are mutually synonymous. Hence, the compiler has no reason to differentiate between them (thus, there can be no polymorphism).

What you really want are two different types that behave differently, for which newtype will do just fine:

newtype AndClause = AndClause [Literal]
newtype OrClause = OrClause [Literal]

instance Satisfiable AndClause where
  satisfy (AndClause l:ls) = --...

instance Satisfiable OrClause where
  satisfy (OrClause l:ls) = --...

But, an even better idea might be to make this an algebraic data type:

data Prop = And [Literal]
          | Or [Literal]

instance Satisfiable Prop where
  satisfy (And l:ls) = --...
  satisfy (Or l:ls) = --...

(Note that I'm typing this away from a compiler, but it should basically be right).