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

[Joshua Ball]

Hi all,

For my own study, I've been playing around with various NP complete
problems. Previuosly I was doing so in Java, but because I want to
learn Haskell, I'm trying to port the algorithms. In Java, I had an
abstract class called AbstractNPProblem which looked like this:

public abstract class AbstractNPProblem implements NPProblem {
    public abstract boolean validates(Certificate c);
    public abstract List<Certificate> certificates();
    public boolean decide() {
        for (Certificate c : certificates()) {
            if (validates(c)) {
                return true;
            }
        }
        return false;
    }
}

This has one problem, however: it is slightly dynamically typed.
Anybody that implements the verify method must cast the object c to a
particular type (could be a bitmask, a list of integers, a subgraph,
etc.) I'd like to get rid of this problem in porting to Haskell. 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)

Could somebody explain what is wrong with my intuitive approach? Also,
is multi parameter type classes the way to go, or is there a better
way?