Overlapping, undecidable, incoherent -- or worse?

Simon Peyton-Jones simonpj at microsoft.com
Thu May 20 09:52:45 EDT 2004

You don't say what you are trying to achieve.  However it looks as if
you mean "If you want PO T, for some type T, first try (Bounded T, Enum
T, SemiRing T) and if that fails try CSemiRing T.  Or maybe the other
way round.

In any case, GHC simply does not implement this kind of backtracking
search.  It would make sense, and some of the more exotic users of type
classes would like it, but (a) there are numerous tricky corners, and
(b) it's awkward to implement the way GHC is now.  If the specification
was completely clear I might be tempted to fix (b), but it isn't.  The
main difficulty is that a compiler does not solve constraints "all at
once".  Instead it does a bit of solving, then then a bit more later.
If the "later" part doesn't pan out, it's jolly difficult to go back to
the original part (in another module, perhaps) and change it. 

As a trivial example, try

	f a = a |= a

What type shall we infer for f?  
	f :: (Bounded a, Enum a, SemiRing a) => a -> a
	f :: (CSemiRing a) => a -> a


| -----Original Message-----
| From: glasgow-haskell-users-bounces at haskell.org
| bounces at haskell.org] On Behalf Of Alex Ferguson
| Sent: 20 May 2004 00:53
| To: glasgow-haskell-users at haskell.org
| Subject: Overlapping, undecidable, incoherent -- or worse?
| The following rings a faint bell from somewhere, but if there's a
| workaround I can't recall or lay my hand on it currently:
| > class PO a where
| >    (|=) :: a -> a -> Bool
| >
| > class Num a => SemiRing a
| >
| > class SemiRing a => CSemiRing a
| >
| > instance (Bounded a, Enum a, SemiRing a) => PO a where
| >    a |= b
| >       = or [ a + c == b | c <- boundedEnumFrom minBound ]
| >
| > instance CSemiRing a => PO a where
| >    a |= b = a + b == b
| The above is in any event requires the "-fallow-undecidable-instances"
| flag, due to the format of the instance clauses, and they're worse
| merely "overlapping" due to the identical heads.  But I'm not quite
| clear why "incoherent" doesn't help here:  isn't the gist of that to
| allow the second to override the first, where they conflict?  Is there
| otherwise a means to have it behave in such a way?
| (I can hack around this by removing the distinction betweem the two
| classes and encoding it as run-time property (which may get compiled
| statically anyway, and I suspect what I actually want are hierarchical
| defaults rather than instances, but that's more like fodder for
| list.)
| Cheers,
| Alex.
| _______________________________________________
| Glasgow-haskell-users mailing list
| Glasgow-haskell-users at haskell.org
| http://www.haskell.org/mailman/listinfo/glasgow-haskell-users

More information about the Glasgow-haskell-users mailing list