Q: Do we include the empty set in the list of subsets?
A: You use whatever subsets are given to you. Your job is to work with the subsets you are given. Not all subsets that are mathematically possible will be there. Consider for example that the Set is a list of necessary vitamins, and each subset represents the vitamins provided by some food, and you need to select the small sequence of foods that provides all the vitamins you need.
NB: The Homework says that maxlist will be useful. Actually, you will need a minlist predicate, that is pretty easy to write once you have maxlist done.
NB: It is permitted to have the same (optimal) cover to be returned more than once.
Q: I have no idea how to write eval.
A: Try some easy cases first. Recall that X+X is short for +(X,X) (see top of page 476). Make sure you handle these easy cases and you will be well on your way. My solution has three cases (three lines). eval is very simple:
Make sure to use recursion to handle subexpressions. Finally remember this is a paper exercise because isNum, add, and mul are difficult/impossible to implement correctly (so that they are invertible).eval(5,5) (should give Yes)
eval([jam,jelly],[jam,jelly]) (should give No)
eval(1+1,2) (should give Yes)
eval(X+1,2) (should give X=1)
Q: What does invertible mean?
A: It means that you can call it with variables and will get all possibilities that would be true. Thus the predicate add could NOT be implemented as
because if someone wrote add(X,X,2) it would crash with the message "insufficiently instantiated." If add were invertible (and you can ASSUME it is when writing eval), you get X=1 as the solution. In other words, this does all the work for you for evaladd(X,Y,Z) :- Z is X + Y. % This WON'T work!
NB: The eval predicate may assume the existence of the add, mul, and isNum predicates. The paper handout gave the impression that eval needed to implement these.