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

[Vladimir Matveev]

Thanks, that was helpful :) here is the working code if someone
interested: http://hpaste.org/fastcgi/hpaste.fcgi/view?id=29406#a29406

2010/8/24 wren ng thornton <wren at freegeek.org>:
> 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
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>