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

[Malcolm Wallace]

Duncan Coutts <duncan.coutts at 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