CODEWITHSUNDEEP
prolog
Bojana Kruzic
Bojana Kruzic

Reputation: 11

operations with sets in prolog

I have seminar paper where I have to find some of the operations with sets in Prolog, for example for subset: 

subset([],V).
subset([H|T1],[H|T2]):-subset(T1,T2).
subset([H1|T1],[H2|T2]):- lt(H2,H1),subset([H1|T1],T2).

I have trouble with finding some of them so I would be very thankful if anyone writes them down:

Upvotes: 1

Views: 7086

Answers (2)

Kaarel
Kaarel

Reputation: 10672

Check out the section library(lists): List Manipulation in the SWI-Prolog manual. Try out the set-specific predicates listed there and check their source code using listing/1, e.g.

?- listing(subset).
lists:subset([], _) :- !.
lists:subset([A|C], B) :-
    memberchk(A, B),
    subset(C, B).

Sets are represented as lists, so to check for members use member/2, to check if a set is empty, check if it unifies with an empty list. To check the nature of the elements of the set, e.g. to see if all are numbers, you can use maplist:

?- maplist(number, [1, -1.2, 0]).
true.

Two sets are equivalent if they are subsets of each other.

Upvotes: 2

pad
pad

Reputation: 41290

In Prolog, set is usually represented by list. So your first listed operation is the member/2 predicate on list, the second is simply checking the set is empty list or not. Some important set-theoretic operations are:

  • union of set A and set B: giving a set containing elements either in A or in B.
  • intersection of A and B: giving a set containing elements both in A and in B.
  • difference of A and B: giving a set containing elements in A and not in B.

Some of those operations are standard operations, for example, description of union/3 and intersection/3 are in Kaarel's link. Some nice discussion about set operations and their implementation in Prolog could be found here: http://kti.mff.cuni.cz/~bartak/prolog/sets.html.

Upvotes: 1

Related Questions