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?
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
