TypeFamilies vs. FunctionalDependencies & type-level recursion

oleg at okmij.org oleg at okmij.org
Wed Jun 22 09:36:33 CEST 2011

> the need to define a duplicate of the class (MonadState' in your
> example) bloats the code significantly.

I'm quite puzzled at the statement. Is there really significant
bloat? Let us count. 

As the first example, let's take
	class C a
with N special instances, mutually non-overlapping instances, and one 
catch-all instance "instance C a". We have N+1 instances total.

With the technique in the earlier message, we define an auxiliary 
	class C' a flag
with N special and one catch-all instance, all non-overlapping. We
then define one instance of the original class C, performing the
dispatch. The additional cost: one class declaration and one
instance. Is one extra class and one instance considered a bloat?
The extra class is systematically derived from the original one
(so, one could get TH to do the deriving).

Let's take a more elaborate example, when all instances overlap, as in

	class C a
	instance C [Int]
	instance C [a]
	instance C a
the flag is not a simple boolean then. We may introduce a special
TYPEREP ANY, and a special TYPEREP comparison function that makes ANY
equal to anything. We will introduce a type family Find that returns
the found element in a list. We will use TYPEREP themselves (with ANY,
as appropriate) to dis-overlap the instances. Although details differ
slightly, the approach applies. The extra cost: one instance and one
class declaration, C'.

> But I am still doubtful of the runtime performance of your code

I believe discussing performance may be a bit premature; keeping in
mind that GHC's support for some of the comparisons may notably affect
the performance. There have been already plans to add Nat kinds to
GHC, presumably with an efficient comparison function.

More information about the Haskell-prime mailing list