[Haskell-cafe] multi parameter type classes for NP problems

[Greg Buchholz]

Joshua Ball wrote:
> Here is how I am trying to solve the problem, using multi-parameter
> type classes.
> 
> class NPProblem inst cert where
>    validates :: cert -> inst -> Bool
>    certificates :: inst -> [cert]
>    decide :: inst -> Bool
>    decide i = any (\x -> x `validates` i) $ certificates i
> 
> Unfortunately, ghc throws the following type error:
> 
> NPProblem.hs:5:45
>    Could not deduce (NPProblem inst a)
>      from the context (NPProblem inst cert)
>      arising from use of `certificates' at NPProblem.hs:5:45-58
>    Possible fix:
>      add (NPProblem inst a) to the class or instance method `decide'
>    In the second argument of `($)', namely `certificates i'
>    In the expression:
>          (any (\ x -> x `validates` i)) $ (certificates i)
>    In the definition of `decide':
>        decide i = (any (\ x -> x `validates` i)) $ (certificates i)

Maybe something like?...

class NPProblem inst cert where
   validates :: cert -> inst -> Bool
   certificates :: inst -> [cert]
   decide :: inst -> Bool
   decide i = any (\x -> x `validates` i) $ (certificates i :: [cert])

...or a functional dependency of some sort...

class NPProblem inst cert | inst -> cert where