[Haskell-cafe] FunDeps and type inference

Olaf Klinke olf at aatal-apotheke.de
Tue Apr 14 21:12:35 UTC 2015

Dear cafe, 

I want to write an evaluation function that uncurries its function argument as necessary. Examples should include: 

eval :: (a -> b) -> a -> b
eval :: (a -> b -> c) -> a -> (b -> c)
eval :: (a -> b -> c) -> (a,b) -> c
and hence have both
eval (+) 4 5
eval (+) (4,5)

My approach is to use a type class:

class Uncurry f a b where
  eval :: f -> a -> b
instance Uncurry (a -> b) a b where
  eval = ($)
instance (Uncurry f b c) => Uncurry ((->) a) f) (a,b) c where
  eval f (a,b) = eval (f a) b

This works, but not for polymorphic arguments. One must annotate function and argument with concrete types when calling, otherwise the runtime does not know what instance to use. 

Type inference on ($) is able to infer the type of either of f, a or b in the expression b = f $ a if the type of two is known. Thus I am tempted to add functional dependencies 

class Uncurry f a b | f a -> b, a b -> f, f b -> a

but I get scary errors: With only the first of the three dependencies, the coverage condition fails. Adding UndecidableInstances, the code compiles. Now type inference on the return type b works, but one can not use e.g. (+) as function argument. Adding the second dependency results in the compiler rejecting the code claiming "Functional dependencies conflict between instance declarations". I can not quite see where they would, and the compiler does not tell me its counterexample. 
I can see that 
eval max (True,False) :: Bool
-- by second instance declaration, 
-- when max :: Bool -> Bool -> Bool
eval max (True,False) :: (Bool,Bool) -> (Bool,Bool) 
-- by first instance declaration
-- when max :: (Bool,Bool) -> (Bool,Bool) -> (Bool,Bool)
but this ambiguity is precisely what the dependency a b -> f should help to avoid, isn't it? 

Judging by the number of coverage condition posts on this list this one is easy to get wrong and the compiler messages are not always helpful. Is this a kind problem? Would anyone care to elaborate? 

Thanks, Olaf

More information about the Haskell-Cafe mailing list