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

Vladimir Matveev dpx.infinity at gmail.com
Mon Aug 23 07:58:32 EDT 2010

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].


[1] http://hpaste.org/fastcgi/hpaste.fcgi/view?id=29380#a29380
[2] http://www.mail-archive.com/haskell-cafe@haskell.org/msg54024.html

More information about the Haskell-Cafe mailing list