[Haskell]
generic currying (type classes and functional dependencies)
Duncan Coutts
duncan.coutts at worcester.oxford.ac.uk
Tue May 11 04:12:33 EDT 2004
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
More information about the Haskell
mailing list