TypeFamilies vs. FunctionalDependencies & type-level recursion

oleg at okmij.org oleg at okmij.org
Thu Jun 23 10:01:11 CEST 2011

> Can you add more special instances for types that match (tm) without using  
> OverlappingInstances and without modifying the instances you have above?

Excellent question, thank you for noticing.

The problem with overlapping instances is that they are ill-founded:
one could potentially add more and more special instances:

	a > [a] > [[a]] > [[[a]]] > ....

GHC could be coerced to choose an instance early (using various
quantification tricks); when a more specialized instances shows up in
another module, which eventually gets linked in into the whole
program, trouble could happen. With type functions, the trouble does
happen, in the form of a segmentation fault. With functional
dependencies, it is not clear what sort of trouble could happen. 
Still, an intuitive behavior could be demonstrated.

The two approaches to tame overlapping instances I know of (closed
type families, instance chains) `close the world'. The programmer must
declare the limit of the specialization chain. The compiler will see
the limit when compiling a module, certain that the limit won't change
in another module. The same approach is implemented in TTypeable.

The type alias

	type Special = StateT_cde :/ NIL

was introduce deliberately. It defines the list of specializations; if
we use the wildcards, the set of types to specialize among could be
infinite, but their lower specialization bound is certain.

To add a new special instance, one does not need to modify any
existing instance in my code. But one has to modify the type alias
Special, adding the TC_code of those special types, or the appropriate

I imagine the type alias Special is in a module of its own, 
placed in a directory named like Config/. A hackage library in general
may have tunable parameters, specific to a particular
installation. These parameters could be collected in Config/*.hs

More information about the Haskell-prime mailing list