
Data Structure

This illustrates a data structure, a means of storing data within a program.

You may see other such structures in the Data Structures category.
A   set  is a collection of elements, without duplicates and without order.



Task

Show each of these set operations:

 Set creation
 Test m ∈ S -- "m is an element in set S"
 A ∪ B -- union; a set of all elements either in set A or in set B.
 A ∩ B -- intersection; a set of all elements in both set A and set B.
 A ∖ B -- difference; a set of all elements in set A, except those in set B.
 A ⊆ B -- subset; true if every element in set A is also in set B.
 A = B -- equality; true if every element of set A is in set B and vice versa.


As an option, show some other set operations.

(If A ⊆ B, but A ≠ B, then A is called a true or proper subset of B, written A ⊂ B or A ⊊ B.)

As another option, show how to modify a mutable set.



One might implement a set using an associative array (with set elements as array keys and some dummy value as the values).

One might also implement a set with a binary search tree, or with a hash table, or with an ordered array of binary bits (operated on with bit-wise binary operators).

The basic test, m ∈ S, is O(n) with a sequential list of elements, O(log n) with a balanced binary search tree, or (O(1) average-case, O(n) worst case) with a hash table.



See also

 Array
 Associative array: Creation, Iteration
 Collections
 Compound data type
 Doubly-linked list: Definition, Element definition, Element insertion, List Traversal, Element Removal
 Linked list
 Queue: Definition, Usage
 Set
 Singly-linked list: Element definition, Element insertion, List Traversal, Element Removal
 Stack


:- use_module(library(lists)).
 
set :-
	A = [2, 4, 1, 3],
	B = [5, 2, 3, 2],
	(   is_set(A) -> format('~w is a set~n', [A])
	;   format('~w is not a set~n', [A])),
	(   is_set(B) -> format('~w is a set~n', [B])
	;   format('~w is not a set~n', [B])),
 
	% create a set from a list
 
	list_to_set(B, BS),
	(   is_set(BS) -> format('~nCreate a set from a list~n~w is a set~n', [BS])
	;   format('~w is not a set~n', [BS])),
 
	intersection(A, BS, I),
	format('~n~w intersection ~w => ~w~n', [A, BS, I]),
	union(A, BS, U),
	format('~w union ~w => ~w~n', [A, BS, U]),
	difference(A, BS, D),
	format('~w difference ~w => ~w~n', [A, BS, D]),
 
	X = [1,2],
	(   subset(X, A) -> format('~n~w is a subset of ~w~n', [X, A])
	;   format('~w is not a subset of ~w~n', [X, A])),
	Y = [1,5],
	(   subset(Y, A) -> format('~w is a subset of ~w~n', [Y, A])
	;   format('~w is not a subset of ~w~n', [Y, A])),
	Z = [1, 2, 3, 4],
	(  equal(Z, A) -> format('~n~w is equal to ~w~n', [Z, A])
	;   format('~w is not equal to ~w~n', [Z, A])),
	T = [1, 2, 3],
	(  equal(T, A) -> format('~w is equal to ~w~n', [T, A])
	;   format('~w is not equal to ~w~n', [T, A])).
 
 
 
% compute difference of sets
difference(A, B, D) :-
	exclude(member_(B), A, D).
 
member_(L, X) :-
	member(X, L).
 
equal([], []).
equal([H1 | T1], B) :-
	select(H1, B, B1),
	equal(T1, B1).
 