11.4 Practical Session 11

Here are some programming exercises:

  1. Sets can be thought of as lists that don't contain any repeated elements. For example, [a,4,6] is a set, but [a,4,6,a] is not (as it contains two occurrences of a). Write a Prolog program subset/2 that is satisfied when the first argument is a subset of the second argument (that is, when every element of the first argument is a member of the second argument). For example:


    Your program should be capable of generating all subsets of an input set by bactracking. For example, if you give it as input


    it should succesively generate all eight subsets of [a,b,c].

  2. Using the subset predicate you have just written, and findall, write a predicate powerset/2 that takes a set as its first argument, and returns the powerset of this set as the second argument. (The powerset of a set is the set of all its subsets.) For example:


    should return

    P = [[],[a],[b],[c],[a,b],[a,c],[b,c],[a,b,c]]

    it doesn't matter if the sets are returned in some other order. For example,

    P = [[a],[b],[c],[a,b,c],[],[a,b],[a,c],[b,c]]

    is fine too.

Patrick Blackburn, Johan Bos and Kristina Striegnitz
Version 1.2.5 (20030212)