[Haskell-cafe] CRIP: the Curiously Reoccuring Instance Pattern

[AntC]

 <oleg <at> okmij.org> writes:

> 
> >
> > I implemented hDeleteMany without FunDeps -- and it works in Hugs (using 
> > TypeCast -- but looks prettier in GHC with equality constraints).
> 
> It is nice that hDeleteMany works on Hugs.  I forgot if we tried it
> back in 2004.

Thanks Oleg -- but it was only 8 years ago ;-)

Yes you did try it: the HList paper gives it as evidence for "We gave up on 
persuading Hugs." and "Overlapping Banned" [Section 6, p7]. I think you were 
premature, which is why I'm using it as an example.

I've also 'repaired' the example in "Ended up in murky water", and got that 
working in Hugs.

Let me say straight away that I'm not trying to 'knock' the work you and Ralf 
put into HList. It's a formidable, and formidably impressive piece of work (as 
can be seen from the number of papers that reference it). I've built record-
like systems using it.

But the HList paper goes on to abandon overlapping, and bring in (essentially) 
the TTypeable approach for type equality. I'm saying (in the discussion a 
couple of months ago) that TTypeable is unnecessary, and that overlapping 
instances are robust -- except when they get mixed up with FunDeps.

I think instead you should have:
- abandoned FunDeps
- embraced Overlapping more!


> To be sure some HList code did work on Hugs. We even had
> a special subset of HList specifically for Hugs (which I removed from
> the distribution some time ago). The problem was that Hugs
> inexplicably would fail in some other HList code. Perhaps 2006 version
> is better in that respect, and more or all of HList would work on it.
> 

Yeah, I'm not trying to 'rehabilitate' Hugs. No point in doing 'compiler 
archeology' on whether/when anything got fixed.

To come back to the CRIP Ryan has spotted:
- It got 'blessed' by SPJ in amongst the 'Records in Haskell' proposals [1]
- Certainly equality constraints make the technique easier;
- but TypeCast (in the HList paper) achieved the same thing back in 2004
  (and the HList paper discusses earlier approaches for typecast).
- So HList used the technique to get round some of the issues with overlapping.
- I'm saying you could have got round more of the issues.
- And perhaps have got the whole of HList working in Hugs.

So here's my conjecture:
1. We don't need FunDeps, except to define TypeCast.
   (And GHC now has equality constraints, which are prettier.)
2. Without FunDeps, overlapping works fine.
3. (Also we don't get into trouble with transitive chains of FunDeps.)
4. Instead of FunDeps, put TypeCasts on all of the instances.
   (Or other Class constraints to 'chain' typevars.)
5. And all of the instances must be framed with a bare typevar in the 'result'.
   (That is, a typevar distinct from any others in the head.)
6. (As you said to Ryan) we still sometimes need repeated typevars in the head,
   for instances that are (in effect) testing for equality.
   But these should only be in the 'argument' position.


AntC

[1] 
http://hackage.haskell.org/trac/ghc/wiki/Records/OverloadedRecordFields#Higherr
anktypesandtypefunctions see "functional-dependency-like mechanism (but using 
equalities)"