[Haskell] generic currying (type classes and functional dependencies)

[Duncan Coutts]

Hi All,

I'm trying to write a generic curry (& uncurry) function that works for
functions of any arity. I have a couple solutions that nearly work, both
involving type classes.

Here's the first one:

class Curry tupled curried where
  genericCurry   :: tupled -> curried
  genericUncurry :: curried -> tupled

The base case is obvious:

instance Curry ((a,b) -> c) (a -> b -> c) where
  genericCurry   f   x y  = f (x,y)
  genericUncurry f' (x,y) = f' x y

However, the inductive case is more tricky. We cannot generically create
tuples of arbitrary size so we'll have to make do with left (or right)
nested pairs. This nesting leads to problems later and for starters
requires overlapping instances:

instance Curry (   (b,c)  -> d) (     b -> c -> d) =>
         Curry ((a,(b,c)) -> d) (a -> b -> c -> d) where
  genericCurry   f  a  b c   = f (a,(b,c))
  genericUncurry f (a,(b,c)) = f  a  b c

This works, but when we come to use it we often run into cases where the
type checker complains with messages such as:
	No instance for (Curry ((Int, Int) -> Int) (a -> b -> Int))
I guess that this is because it fails to be able to convince itself that
a & b are Int, in which case there would be an instance. This can be
solved by supplying enough type annotations, however this is annoying
and part of the point of a generic curry is that we don't know the arity
of the function to which we are applying it.

So I thought that functional dependencies might help because the curried
type should uniquely determine the uncurried type (and vice versa).
However if I change the class declaration to:

class Curry tupled curried | tupled -> curried, curried -> tupled  where
  genericCurry   :: tupled -> curried
  genericUncurry :: curried -> tupled

Then the compiler complains about my instance declarations:

Functional dependencies conflict between instance declarations:
      ./Curry.hs:11:0: instance Curry ((a, b) -> c) (a -> b -> c)
      ./Curry.hs:16:0:
        instance (Curry ((b, c) -> d) (b -> c -> d)) =>
                 Curry ((a, (b, c)) -> d) (a -> b -> c -> d)

I don't fully understand why this is the case, but it is to do with the
nested pairing, because individual instance declarations for 3-tuples,
4-tuples work find.

Any insight or suggestions would be interesting.

Duncan