[Haskell] generic currying (type classes and functional dependencies)
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
Duncan Coutts <duncan.coutts@worcester.oxford.ac.uk> writes:
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 fine.
With a little alpha-renaming: instance Curry ((a, b) -> c) (a -> b -> c) instance (Curry ((e, f) -> g) (e -> f -> g)) => Curry ((d, (e, f)) -> g) (d -> e -> f -> g) It should be fairly easy to see that the type (d, (e, f)) -> g is an instance of (a, b) -> c where a==d and b==(e,f) and c==g. Also (d -> e -> f -> g) is an instance of (a -> b -> c) where a=d and b==e and c==(f->g). So for one thing your two instances overlap, but additionally, the type-variables do not unify, because in the tupled part of the Curry predicate, b==(e,f), but in the curried part of the predicate, b==e. Regards, Malcolm
In message <1084241553.27784.25.camel@localhost>, Duncan Coutts writes:
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. [SNIP] Any insight or suggestions would be interesting.
Here's one solution, which I think is more general than what you ask, but I guess it should work as well. It's based on adjunctions from category theory: class (Functor path, Functor space) => Adjunction path space | path -> space, space -> path where leftAdjunct :: (path top -> bot) -> top -> space bot unit :: top -> space (path top) rightAdjunct :: (top -> space bot) -> path top -> bot counit :: path (space bot) -> bot -- minimum required impl: unit xor leftAdjunct -- minimum required impl: counit xor rightAdjunct unit = leftAdjunct id leftAdjunct f = fmap f . unit counit = rightAdjunct id rightAdjunct g = counit . fmap g -- Here are some instances for different arities: instance Adjunction ((,) a) ((->) a) where unit t = \arg -> (arg,t) counit (x,f) = f x newtype Func2 a b c = Func2 (a -> b -> c) -- Func2 is only needed due to syntax of partial type constructor application instance Adjunction ((,,) a b) (Func2 a b) where unit t = Func2 (\arg1 arg2 -> (arg1,arg2,t)) counit (arg1,arg2,Func2 f) = f arg1 arg2 instance Functor ((,,) a b) where fmap f (x,y,z) = (x,y,f z) instance Functor (Func2 a b) where fmap f (Func2 g) = Func2 (\a b -> f (g a b)) Here, 'leftAdjunct' is a generalization of curry and rightAdjunct is a generalization of uncurry. -- Esa Pulkkinen
Duncan Coutts writes (to the Haskell Mailing list):
I'm trying to write a generic curry (& uncurry) function that works for functions of any arity.
See <http://www.haskell.org/pipermail/haskell/2003-April/011720.html> where oleg presents a (ghc-specific) solution. Cheers, Ronny Wichers Schreur
participants (4)
-
Duncan Coutts -
Esa Pulkkinen -
Malcolm Wallace -
Ronny Wichers Schreur