[haskell-cafe] How to substitute FD like a -> b c by type
wren ng thornton
wren at freegeek.org
Mon Aug 23 23:56:31 EDT 2010
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 . 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" .
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.
More information about the Haskell-Cafe