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@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
