
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


[<EntryPoint>]
let main args =
    // Create some sets (of int):
    let s1 = Set.ofList [1;2;3;4;3]
    let s2 = Set.ofArray [|3;4;5;6|]
 
    printfn "Some sets (of int):"
    printfn "s1 = %A" s1
    printfn "s2 = %A" s2
    printfn "Set operations:"
    printfn "2 ∈ s1? %A" (s1.Contains 2)
    printfn "10 ∈ s1? %A" (s1.Contains 10)
    printfn "s1 ∪ s2 = %A" (Set.union s1 s2)
    printfn "s1 ∩ s2 = %A" (Set.intersect s1 s2)
    printfn "s1 ∖ s2 = %A" (Set.difference s1 s2)
    printfn "s1 ⊆ s2? %A" (Set.isSubset s1 s1)
    printfn "{3, 1} ⊆ s1? %A" (Set.isSubset (Set.ofList [3;1]) s1)
    printfn "{3, 2, 4, 1} = s1? %A" ((Set.ofList [3;2;4;1]) = s1)
    printfn "s1 = s2? %A" (s1 = s2)
    printfn "More set operations:"
    printfn "#s1 = %A" s1.Count
    printfn "s1 ∪ {99} = %A" (s1.Add 99)
    printfn "s1 ∖ {3} = %A" (s1.Remove 3)
    printfn "s1 ⊂ s1? %A" (Set.isProperSubset s1 s1)
    printfn "s1 ⊂ s2? %A" (Set.isProperSubset s1 s2)
    0