[Haskell-cafe] Are type synonym families really equivalent to fundeps?

Chris Smith cdsmith at twu.net
Mon Sep 3 17:43:56 EDT 2007

The following code builds and appears to work great (assuming one allows 
undecidable instances).  I have tried both a natural translation into 
type synonym families, and also the mechanical transformation in 
http://www.cse.unsw.edu.au/~chak/papers/tyfuns.pdf -- but I can't get 
either to work.

The two fishy things are:

1. There is a functional dependency (a -> t) in the original.  Actually, 
this isn't always true since t is sometimes not uniquely determined by 
a; but GHC always seems to do the right thing anyway.  There doesn't 
seem to be any way to "cheat" like this with type families.

2. In the second and fourth instances, the type variable x appears twice 
in the parameters of the type function built from the fundep (a b -> c).  
This causes an error.  If I try adding (x ~ x') to the context and 
making one of them x' instead of x, I get different errors.

I'm starting to this this is an example of using functional dependencies 
that has no translation to type families.  Can anyone free me of such 

Code with fundeps is:

  data Var a  = Var Int (Maybe String)
  data RHS a b = RHS a b

  class Action t a b c | a -> t, a b -> c, a c -> b
  instance                     Action  t  ()               y         y
  instance                     Action  t  (Var x)          (x -> y)  y
  instance                     Action  t  [t]              y         y
  instance (Action t a b c) => Action  t  (RHS (Var x) a)  (x -> b)  c
  instance (Action t a b c) => Action  t  (RHS [t]     a)  b         c

Chris Smith

More information about the Haskell-Cafe mailing list