[Haskell-cafe] Class of ordered tuples

Olaf Klinke olf at aatal-apotheke.de
Mon Sep 16 19:08:01 UTC 2019

Dear Cafe, 

I had a lengthy discussion with GHC but so far it won't let me do the following. (Code below is simplified to transport the idea. Type families don't seem to do the trick, either.)
A finite set of types A, B, C, ... is totally ordered. This can be expressed e.g. by a multi-parameter type class and type-level natural numbers:

instance Index A 0 where
instance Index B 1 where

Now I want a type class Range and an appropriate set of instance declarations that has
A, B, (A,B), (A,C), (A,(B,C)) etc. as members but not
(B,A) or (C,C). That is, each type appears at most once and in the defined order. 

The problem is overlapping instances of the base case with the inductive case. 

instance Index a n => Range a n n
instance (Range a x y, Range b x' y', y < x') => Range (a,b) x y'

Then the compiler rightfully complains that someone could write an instance Index (a,b) n
which would lead to conflicting instances of Range (a,b) n n. I can not make either of the type classes Index nor Range closed because there will be several of those sets of types. This problem is like smart constructors for ordered lists, but on the type level. 

Thanks in advance for any hints.

More information about the Haskell-Cafe mailing list