Bidirectional Functional Dependencies

Question

I have a type class that looks a bit like the following:

class Foo a b | a -> b where
  f :: a -> Bool
  g :: b -> Bool
  h :: a -> b -> Bool

Or at least these are the bits that are important to my question. This class does not compile, and for good reason. The problem with this class is that I could (if I wanted to) do the following:

instance Foo () Bool where
  f x = True
  g y = y
  h x y = False

instance Foo ((), ()) Bool where
  f x = True
  g y = not y
  h x y = False

Now if I call g True there are two separate results one for each instance. And the compiler picks up on this possibility and informs me that my type class is no good.

My issue is that the dependency | a -> b is not quite what I mean. I don't just mean that you can find a from b, but also that you can find b from a. That is each type should only ever be a member of Foo with one other type so we can given one type find the other. Or to put it in yet another way the dependency is bidirectional. Such a functional dependency would prevent me from having Bool present in two separate instances because the first parameter would be derivable from the second as well as the second from the first.

But I don't know how to express this idea to the compiler.

How can I create a bidirectional functional dependency? Or, more likely, is there a way that I can rephrase my type class to get something that could replace a bidirectional functional dependency?

Answer 1

A bidirectional dependency between a and b can be presented as two functional dependencies a -> b and b -> a, like:

class Foo a b | a -> b, b -> a where
  f :: a -> Bool
  g :: b -> Bool
  h :: a -> b -> Bool

So here a is functional dependent on b and b is functional dependent on a.

For your instances however this of course raises an error, since now you defined two different as for b ~ Bool. This will raise an error like:

file.hs:6:10: error:
    Functional dependencies conflict between instance declarations:
      instance Foo () Bool -- Defined at file.hs:6:10
      instance Foo ((), ()) Bool -- Defined at file.hs:11:10
Failed, modules loaded: none.

Because of the functional dependency, you can only define one a for b ~ Bool. But this is probably exactly what you are looking for: a mechanism to prevent defining Foo twice for the same a, or the same b.