[haskell-cafe] How to substitute FD like a -> b c by type families?

[wren ng thornton]

Vladimir Matveev wrote:
> I'm trying to implement the "Advanced Example : Type-Level Quicksort"
> from HaskellWiki using type families instead of functional
> dependencies. My code is at [1]. I substituted all 'many to one'
> functional dependencies like xs ys -> zs by explicit type families,
> but I don't know how to replace 'many to many' dependencies by type
> families only, so I've used associated types. But for some unknown to
> me reason the typechecker hangs if I try to get listQuickSort type
> signature in ghci.
> So I have 2 questions: what is the correct replacement of FDs in this
> case and where is an error in my code? I assume that the correct
> replacement exists (though it may not be very pretty) because "type
> families and  functional dependencies are equivalent in
> expressiveness" [2].

I'm no guru on TF/ATs, but it seems to me that the simplest translation 
from fundeps would be to use multiple different type families for 
getting each of the result types. Thus,

     class Foo a b c ... x y z | a b c ... -> ... x y z

is first interpreted as:

     class Foo a b c ... x y z
         | ...
         , a b c ... -> x
         , a b c ... -> y
         , a b c ... -> z

which then becomes:

     ...
     type family FooX a b c ...
     type family FooY a b c ...
     type family FooZ a b c ...

This is equivalent to converting a function of type 
(A,B,C,...)->(...,X,Y,Z) into multiple functions for determining each 
member of the output tuple separately. Your version using ATs to shove 
all the results into the Pick and Split classes is equivalent to 
constructing the output tuple directly. Apparently that doesn't work out 
for some reason.

-- 
Live well,
~wren