
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


 
Module Sets {
	setA=("apple", "cherry", "grape")
	setB=("banana","cherry", "date")
 
	Print Len(setA)=3 'true
	Print setA#pos("apple")>=0=true   ' exist
	Print setA#pos("banana")>=0=False  ' not exist
 
	intersection=lambda  SetB (x$)-> SetB#pos(x$)>=0
	SetC=SetA#filter(intersection,(,))
	Print SetC
 
	Difference= lambda (aSet)->{
		=lambda  aSet (x$)-> aSet#pos(x$)<0
	}
	IsetC=SetB#filter(Difference(setA),(,))
	Print SetC
	SetC=SetA#filter(Difference(setB),(,))
	Print SetC
 
	k=each(setB)
	SetC=cons(setA)
	while k
		if setA#pos(SetB#val$(k^))<0 then Append SetC, (SetB#val$(k^),)
	end while
	Print SetC
	\\ subset if items exists in same order
	Print SetA#pos("cherry","grape")>=0 ' true ' is a subset of SetA
	Print SetA#pos(("apple", "cherry"))>=0 ' true ' is a subset of SetA
	Print SetA#pos(("apple","grape"))>=0 ' false ' is not a subset of SetA in that order
	\\ subset in any position
	fold1=lambda (aSet)-> {
		=lambda aSet (x$, cond) ->{
			push cond and aSet#pos(x$)>=0
		}
	}
	SetC=("banana", "date")
	print SetC#Fold(fold1(SetA), True)  ' False
	print SetC#Fold(fold1(SetB), True)  ' True
	SetC=("cherry",)
	print SetC#Fold(fold1(SetA), True)  ' True
	print SetC#Fold(fold1(SetB), True)  ' True
	\\ Mutation
	\\ change value at position 0
	return SetC, 0:="banana"
	print SetC#Fold(fold1(SetA), True)  ' False
	print SetC#Fold(fold1(SetB), True)  ' True
 
	\\ equality
	SetC=Cons(SetA)  ' we get a copy of one or more tuple
	\\ SetC is subset of SetA and SetA is subset of  SetC
	Print SetC#Fold(fold1(SetA), True)=SetA#Fold(fold1(SetC), True)  ' True
	\\ another way
	Print Len(SetC#filter(Difference(setA),(,)))=0   ' true   \\ difference is an empty tuple
	append SetC, SetB
	Print Len(SetC)=6 ' true
	print SetC#pos(0 ->"cherry")=1 ' true
	print SetC#pos(2 -> "cherry")=4 ' true
	print SetC#pos(5 -> "cherry")=-1 ' true
	print SetC#pos(0 -> "banana","cherry")=3 ' true
	print SetC#pos( "banana","cherry")=3 ' true
	mapU=lambda ->{
		push ucase$(letter$)
	}
	fold2=lambda (x$, k$)->{
		push replace$(")(", ", ",k$+"("+quote$(x$)+")")
	}
	Print SetC#map(mapU)#fold$(fold2, "") ' ("APPLE", "CHERRY", "GRAPE", "BANANA", "CHERRY", "DATE")
	Print SetC#map(mapU)  ' APPLE CHERRY GRAPE BANANA CHERRY DATE
	Print SetC#fold$(fold2, "")  ' ("apple", "cherry", "grape", "banana", "cherry", "date")
 
}
Sets
 