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