GHC: Ticket #1894: Add a total order on type constructors
http://ghc.haskell.org/trac/ghc/ticket/1894
<p>
Several proposals for <a class="wiki" href="http://ghc.haskell.org/trac/ghc/wiki/ExtensibleRecords">ExtensibleRecords</a> can be implemented as libraries if type constructors can be ordered globally.
</p>
<p>
This proposal is to add built-in types:
</p>
<pre class="wiki">data LabelLT
data LabelEQ
data LabelGT
type family LabelCMP
</pre><p>
such that, for any two datatypes
</p>
<pre class="wiki">data N = N
data M = M
</pre><p>
the instance <tt>LabelCMP N M</tt> takes one of the values <tt>LabelLT, LabelEQ, LabelGT</tt> depending on the lexicographic ordering on the fully-qualified names of <tt>N</tt> and <tt>M</tt>.
</p>
en-usGHChttp://ghc.haskell.org/trac/ghc/chrome/site/ghc_logo.png
http://ghc.haskell.org/trac/ghc/ticket/1894
Trac 1.0.1guestThu, 15 Nov 2007 11:00:09 GMTcc set
http://ghc.haskell.org/trac/ghc/ticket/1894#comment:1
http://ghc.haskell.org/trac/ghc/ticket/1894#comment:1
<ul>
<li><strong>cc</strong>
<em>b.hilken@…</em> added
</li>
</ul>
TicketsorearThu, 15 Nov 2007 23:52:29 GMTcc changed; difficulty set
http://ghc.haskell.org/trac/ghc/ticket/1894#comment:2
http://ghc.haskell.org/trac/ghc/ticket/1894#comment:2
<ul>
<li><strong>cc</strong>
<em>sorear</em> added
</li>
<li><strong>difficulty</strong>
set to <em>Unknown</em>
</li>
</ul>
<p>
I hate this proposal, but something like it is dearly needed, and I don't want to see yet another bikeshed war. Adding myself to the CC.
</p>
TicketclausSat, 17 Nov 2007 17:39:53 GMT
http://ghc.haskell.org/trac/ghc/ticket/1894#comment:3
http://ghc.haskell.org/trac/ghc/ticket/1894#comment:3
<p>
the ticket neglects to mention that at least one of the record libraries under discussion does not need such an ordering.
</p>
<p>
that does not imply that the feature might not be useful, and most of the record libraries do indeed employ such an ordering. but, as any other form of reflection, it would have to be designed very carefully: one usually cannot avoid destroying at least some program equivalences when introducing reflection, so at the very least, one needs to be able to separate programs that use such feature (where those equivalences will fail) from programs that do not (where reasoning about programs is not affected).
</p>
<p>
examples of equivalences no longer valid under this proposal are renaming types or modules and moving types or modules in the module hierarchy.
</p>
<p>
perhaps type-level ordering should only be available for members of a type class, such as the existing <tt>Data</tt> or <tt>Typeable</tt>? and perhaps it should be based on random uniqueIds, similar to <tt>Data.Typeable.typeRepKey</tt>? but that has its own issues..
</p>
<p>
@GHC-HQ:
how do i add myself to the cc without voting in favour? should there be two cc-lists?-)
</p>
TicketguestSat, 17 Nov 2007 17:57:18 GMT
http://ghc.haskell.org/trac/ghc/ticket/1894#comment:4
http://ghc.haskell.org/trac/ghc/ticket/1894#comment:4
<p>
The problem with using uniqIds is that the order used when a module is compiled must be the same as the order used when it is imported. Do the existing uniqIds have that property?
</p>
<p>
The suggestion to restrict this to a special type-class is a good one. Maybe this should be done as a special kind of <tt>deriving</tt>. I would prefer a new class to an extension of an existing one.
</p>
TicketsorearSat, 17 Nov 2007 19:04:51 GMT
http://ghc.haskell.org/trac/ghc/ticket/1894#comment:5
http://ghc.haskell.org/trac/ghc/ticket/1894#comment:5
<p>
Replying to <a class="new" href="http://ghc.haskell.org/trac/ghc/ticket/1894#comment:4" title="Comment 4 for Ticket #1894">guest</a>:
</p>
<blockquote class="citation">
<p>
The suggestion to restrict this to a special type-class is a good one. Maybe this should be done as a special kind of <tt>deriving</tt>. I would prefer a new class to an extension of an existing one.
</p>
</blockquote>
<p>
There is always Oleg's TTypeable (which Data.Derive can handle); otoh, it uses fundeps.
</p>
<p>
Chakravarty: Is it feasable to make fundeps and type families 'compatible' in the sense that either can depend on the other?
</p>
TicketiglooSat, 17 Nov 2007 22:52:26 GMTmilestone set
http://ghc.haskell.org/trac/ghc/ticket/1894#comment:6
http://ghc.haskell.org/trac/ghc/ticket/1894#comment:6
<ul>
<li><strong>milestone</strong>
set to <em>6.10 branch</em>
</li>
</ul>
TicketsimonmarTue, 30 Sep 2008 15:45:14 GMTarchitecture changed
http://ghc.haskell.org/trac/ghc/ticket/1894#comment:7
http://ghc.haskell.org/trac/ghc/ticket/1894#comment:7
<ul>
<li><strong>architecture</strong>
changed from <em>Multiple</em> to <em>Unknown/Multiple</em>
</li>
</ul>
TicketsimonmarTue, 30 Sep 2008 15:54:51 GMTos changed
http://ghc.haskell.org/trac/ghc/ticket/1894#comment:8
http://ghc.haskell.org/trac/ghc/ticket/1894#comment:8
<ul>
<li><strong>os</strong>
changed from <em>Multiple</em> to <em>Unknown/Multiple</em>
</li>
</ul>
TicketiglooSun, 12 Apr 2009 20:27:22 GMTmilestone changed
http://ghc.haskell.org/trac/ghc/ticket/1894#comment:9
http://ghc.haskell.org/trac/ghc/ticket/1894#comment:9
<ul>
<li><strong>milestone</strong>
changed from <em>6.10 branch</em> to <em>6.12 branch</em>
</li>
</ul>
TicketiglooFri, 30 Apr 2010 16:39:19 GMTmilestone changed
http://ghc.haskell.org/trac/ghc/ticket/1894#comment:10
http://ghc.haskell.org/trac/ghc/ticket/1894#comment:10
<ul>
<li><strong>milestone</strong>
changed from <em>6.12 branch</em> to <em>6.12.3</em>
</li>
</ul>
TicketiglooSat, 19 Jun 2010 16:56:53 GMTpriority, milestone changed
http://ghc.haskell.org/trac/ghc/ticket/1894#comment:11
http://ghc.haskell.org/trac/ghc/ticket/1894#comment:11
<ul>
<li><strong>priority</strong>
changed from <em>normal</em> to <em>low</em>
</li>
<li><strong>milestone</strong>
changed from <em>6.12.3</em> to <em>6.14.1</em>
</li>
</ul>
TicketiglooSun, 19 Dec 2010 17:45:59 GMTmilestone changed
http://ghc.haskell.org/trac/ghc/ticket/1894#comment:12
http://ghc.haskell.org/trac/ghc/ticket/1894#comment:12
<ul>
<li><strong>milestone</strong>
changed from <em>7.0.1</em> to <em>7.0.2</em>
</li>
</ul>
TicketiglooSat, 05 Mar 2011 13:16:13 GMTmilestone changed
http://ghc.haskell.org/trac/ghc/ticket/1894#comment:13
http://ghc.haskell.org/trac/ghc/ticket/1894#comment:13
<ul>
<li><strong>milestone</strong>
changed from <em>7.0.2</em> to <em>7.2.1</em>
</li>
</ul>
TicketiglooSat, 01 Oct 2011 23:16:25 GMTmilestone changed
http://ghc.haskell.org/trac/ghc/ticket/1894#comment:14
http://ghc.haskell.org/trac/ghc/ticket/1894#comment:14
<ul>
<li><strong>milestone</strong>
changed from <em>7.2.1</em> to <em>7.4.1</em>
</li>
</ul>
TicketnfrisbyWed, 07 Dec 2011 17:16:24 GMTfailure set
http://ghc.haskell.org/trac/ghc/ticket/1894#comment:15
http://ghc.haskell.org/trac/ghc/ticket/1894#comment:15
<ul>
<li><strong>failure</strong>
set to <em>None/Unknown</em>
</li>
</ul>
<p>
Summary: I think type-level digits/numerals and a type-level reflection of the globally unique-name as a type-level numeral would subsume the proposed functionality.
</p>
<p>
(This ticket seems quite stale — has there been any more decisions regarding this?)
</p>
<p>
If the ordering can be arbitrary, I think type-level serializations fit the bill. I chose to "serialize" the types as their global names, so the order of compilation shouldn't matter — everything is based on GUIDs. (I don't think this address Reinke's program logic concerns.)
</p>
<p>
For the details, see my Hackage packages type-cereal, type-ord, and type-ord-spine-cereal which rely on type-spine and type-digits.
</p>
<ul><li>type-digits declares a fixed set of type-level digits (* -> *, terminated with ()) and means to build numerals from them
</li><li>type-ord declares LabelCMP (as Compare) with instances for each pair of those digits and ((), ())
</li><li>type-cereal declares a type family Serialize and a (TH) function for representing bytestrings as type-level numerals (to hijack the cereal package's serialization)
</li><li>type-spine declares a type-level "spine-view"
</li><li>type-ord-spine-cereal declares "generic" LabelCMP instances using the spine-view to reduce all (spine-view-enabled) types to applications of serializable names and then uses the type-digits' LabelCMP instances and a "lexicographic" instance for type-level applications
</li></ul>
TicketiglooFri, 10 Feb 2012 16:14:33 GMTpriority, milestone changed
http://ghc.haskell.org/trac/ghc/ticket/1894#comment:16
http://ghc.haskell.org/trac/ghc/ticket/1894#comment:16
<ul>
<li><strong>priority</strong>
changed from <em>low</em> to <em>lowest</em>
</li>
<li><strong>milestone</strong>
changed from <em>7.4.1</em> to <em>7.6.1</em>
</li>
</ul>
TicketiglooWed, 12 Sep 2012 11:13:44 GMTmilestone changed
http://ghc.haskell.org/trac/ghc/ticket/1894#comment:17
http://ghc.haskell.org/trac/ghc/ticket/1894#comment:17
<ul>
<li><strong>milestone</strong>
changed from <em>7.6.1</em> to <em>7.6.2</em>
</li>
</ul>
TicketmorabbinSat, 26 Jan 2013 22:56:34 GMT
http://ghc.haskell.org/trac/ghc/ticket/1894#comment:18
http://ghc.haskell.org/trac/ghc/ticket/1894#comment:18
<p>
Bump; how does this fare given the last five years of type system extensions? (Still ref'd in <a class="wiki" href="http://ghc.haskell.org/trac/ghc/wiki/ExtensibleRecords">ExtensibleRecords</a>.)
</p>
TicketgoldfireSun, 27 Jan 2013 04:04:49 GMT
http://ghc.haskell.org/trac/ghc/ticket/1894#comment:19
http://ghc.haskell.org/trac/ghc/ticket/1894#comment:19
<p>
As far as I can see, the evolution of the type system hasn't fundamentally changed this issue. With closed kinds (i.e., those from a promoted datatype), it is easy to define an ordering using a type family. But, that doesn't solve the problem for kind <tt>*</tt>.
</p>
<p>
There is a chance that any applications that want this feature can use nfrisby's packages, or the upcoming TypeLits work, which includes type-level strings.
</p>
<p>
Is there anyone out there who still needs this? What's your application?
</p>
TicketthoughtpoliceMon, 14 Jul 2014 13:07:28 GMTmilestone changed
http://ghc.haskell.org/trac/ghc/ticket/1894#comment:20
http://ghc.haskell.org/trac/ghc/ticket/1894#comment:20
<ul>
<li><strong>milestone</strong>
changed from <em>7.6.2</em> to <em>7.10.1</em>
</li>
</ul>
<p>
Moving to 7.10.1.
</p>
TicketthoughtpoliceTue, 23 Dec 2014 13:33:22 GMTmilestone changed
http://ghc.haskell.org/trac/ghc/ticket/1894#comment:21
http://ghc.haskell.org/trac/ghc/ticket/1894#comment:21
<ul>
<li><strong>milestone</strong>
changed from <em>7.10.1</em> to <em>7.12.1</em>
</li>
</ul>
<p>
Moving to 7.12.1 milestone; if you feel this is an error and should be addressed sooner, please move it back to the 7.10.1 milestone.
</p>
TicketthoughtpoliceTue, 23 Dec 2014 13:33:22 GMT
http://ghc.haskell.org/trac/ghc/ticket/1894#comment:22
http://ghc.haskell.org/trac/ghc/ticket/1894#comment:22
<p>
Moving to 7.12.1 milestone; if you feel this is an error and should be addressed sooner, please move it back to the 7.10.1 milestone.
</p>
Ticket