#15493: Elide empty dictionaries -------------------------------------+------------------------------------- Reporter: mnoonan | Owner: (none) Type: feature request | Status: new Priority: normal | Milestone: 8.6.1 Component: Compiler | Version: 8.4.3 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by Iceland_jack): See discussion in [https://repository.brynmawr.edu/cgi/viewcontent.cgi?article=1075&context=compsci_pubs goldfire's "Constrained Type Families"], subsection **7.3 Runtime Efficiency**
Constrained type families may also seem to have a non-trivial efficiency impact. For a simple example, suppose we have a type family `F`, and consider an existentially-packaged type family application:
{{{#!hs data FPack a where FPack :: F a -> FPack a }}}
We might expect an `FPack a` value to contain exactly a value of type `F a`. With constrained type families, however, the declaration above would be incorrect; we would need to add a predicate for its constraining class, say `C`:
{{{#!hs data FPack1 a where FPack1 :: C a => F a -> FPack1 a }}}
Now, a value of type `FPack1 a` does not just contain an `F a` value, but must also carry a `C a` dictionary, and uses of `FPack1` will be responsible for constructing, packing, and unpacking these dictionaries. Over sufficiently many uses of `FPack1`, this additional cost could be noticeable.
This efficiency impact can be mitigated, however. This issue can crop up only when we have a value of type `F a` (or other type family application) without an instance of the associated class `C a`. But in order for the value of type `F a` to be useful, parametricity tells us that `C a`, or some other class with a similar structure to the equations for `F a` must be in scope. Barring this, it must be that `F a` is used as a phantom type. In this case, we would want a “phantom dictionary” for `C a`, closely paralleling existing work on proof irrelevance in the dependently- typed programming community (..): the `C a` dictionary essentially represents a proof that will never be examined. While we do not propose here a new solution to this problem, we believe that existing work will be applicable in our case as well.
-- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/15493#comment:3 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler