▼Functional Data Structures in Typed Racket
On this page:
Set
set
empty?
insert
member?
subset?
union
intersection
difference
set->list
map
filter
remove
Version: 5.0.1.3
  ← prev  up  next → 

10 Sets

 (require (planet krhari/pfds:1:4/set))

An simple implementation of sets based on binary trees.

(Set A)
A set of type A.

(set comp a ...) → (Set A)
  comp : (A A -> Boolean)
  a : A
Function set creates a Set with the given inputs. The function requires a comparison function as in this implementation, data is maintained in the form of a binary tree which has a lot of advantages over a naive set implementation using lists.

Example:

  > (set < 1 2 3 4 5)

  - : (Set Positive-Fixnum)

  #<Set>

In the above example, the set obtained will have 2 as its root and < as the comparison function.

(empty? set) → Boolean
  set : (Set A)
Function empty? checks if the given set is empty.

Examples:

  > (empty? (set < 1 2 3 4 5 6))

  - : Boolean

  #f

  > (empty? (set <))

  - : Boolean

  #t

(insert a set) → (Set A)
  a : A
  set : (Set A)
Function insert inserts the given element into the set. If the given element is alredy in the set, it just ignores it i.e. the elements of the set are not duplicated.

Examples:

  > (insert 10 (set < 1 2 3 4 5 6))

  - : (Set Positive-Fixnum)

  #<Set>

  > (insert 1 (set < 1 2 3 4 5 6))

  - : (Set Positive-Fixnum)

  #<Set>

In the first example, insert adds the 10 to (set < 1 2 3 4 5 6). In the second example, it just returns (set < 1 2 3 4 5 6).

(member? set) → Boolean
  set : (Set A)
Function member? takes an element and a set and checks if the given element is a member of the set.

Examples:

  > (member? 5 (set < 1 2 3 4 5 6))

  - : Boolean

  #t

  > (member? 10 (set < 1 2 3 4 5 6))

  - : Boolean

  #f

(subset? set1 set2) → Boolean
  set1 : (Set A)
  set2 : (Set A)
Function subset? checks if set2 is a subset of set1.

Examples:

  > (subset? (set < 1 2 3 4 5 6) (set < 7 8 9))

  - : Boolean

  #f

  > (subset? (set < 1 2 3 4 5 6) (set < 1 2 3 4 5 6))

  - : Boolean

  #t

  > (subset? (set < 1 2 3 4 5 6) (set < 2 3))

  - : Boolean

  #t

  > (subset? (set < 1 2 3 4 5 6) ((inst set Positive-Fixnum) <))

  - : Boolean

  #t

In the last example we are instantiating the set to be of type Positive-Fixnum as it cannot be inferred because of the absence of elements.

(union set1 set2) → (Set A)
  set1 : (Set A)
  set2 : (Set A)
Function union returns the union of the two given sets.

Examples:

  > (union (set < 1 2 3 4 5 6) (set < 7 8 9))

  - : (Set Positive-Fixnum)

  #<Set>

  > (union (set < 1 2 3 4 5 6) (set < 1 2 3 4 5 6))

  - : (Set Positive-Fixnum)

  #<Set>

In the first example, union returns (set < 1 2 3 4 5 6 7 8 9), and in the second example it returns (set < 1 2 3 4 5 6)

(intersection set1 set2) → (Set A)
  set1 : (Set A)
  set2 : (Set A)
Function intersection returns the common elements of the two given sets.

Examples:

  > (intersection (set < 1 2 3 4 5 6) (set < 7 8 9))

  - : (Set Positive-Fixnum)

  #<Set>

  > (intersection (set < 1 2 3 4 5 6) (set < 1 2 3 4 5 6))

  - : (Set Positive-Fixnum)

  #<Set>

  > (intersection (set < 1 2 3 4 5 6) (set < 2 3 10 15))

  - : (Set Positive-Fixnum)

  #<Set>

In the first example, intersection returns a empty set, and in the second example it returns (set < 1 2 3 4 5 6) and in the third, it returns (set < 2 3)

(difference set1 set2) → (Set A)
  set1 : (Set A)
  set2 : (Set A)
Function difference returns all the elements in first set that are not in the second set.

Examples:

  > (difference (set < 1 2 3 4 5 6) (set < 7 8 9))

  - : (Set Positive-Fixnum)

  #<Set>

  > (difference (set < 1 2 3 4 5 6) (set < 1 2 3 4 5 6))

  - : (Set Positive-Fixnum)

  #<Set>

  > (difference (set < 1 2 3 4 5 6) (set < 2 3 10 15))

  - : (Set Positive-Fixnum)

  #<Set>

In the first example, difference returns (set < 1 2 3 4 5 6), and in the second example it returns a empty set and in the third, it returns (set < 1 4 5 6)

(set->list set) → (Listof A)
  set : (Set A)
Function set->list takes a set and returns a list containing all the elements of the given set.

Example:

  > (set->list (set > 1 2 3 4 5))

  - : (Listof Positive-Fixnum)

  '(5 4 3 2 1)

(map comparer func set1 set2 ...) → (Set A)
  comparer : (C C -> Boolean)
  func : (A B ... B -> C)
  set1 : (Set A)
  set2 : (Set B)
Function map is similar to map for lists.

Examples:

  > (set->list (map < add1 (set < 1 2 3 4 5 6)))

  - : (Listof Exact-Positive-Integer)

  '(2 3 4 5 6 7)

  > (set->list (map < *
                    (set < 1 2 3 4 5 6)
                    (set < 1 2 3 4 5 6)))

  - : (Listof Exact-Positive-Integer)

  '(1 4 9 16 25 36)

(filter func set) → (Set A)
  func : (A -> Boolean)
  set : (Set A)
Function filter is similar to filter.

Examples:

  > (set->list (filter (λ: ([x : Integer]) (> x 5))
                       (set < 1 2 3 4 5 6)))

  - : (Listof Positive-Fixnum)

  '(6)

  > (set->list (filter (λ: ([x : Integer]) (< x 5))
                       (set < 1 2 3 4 5 6)))

  - : (Listof Positive-Fixnum)

  '(1 2 3 4)

  > (set->list (filter (λ: ([x : Integer]) (<= x 5))
                       (set < 1 2 3 4 5 6)))

  - : (Listof Positive-Fixnum)

  '(1 2 3 4 5)

(remove func set) → (Set A)
  func : (A -> Boolean)
  set : (Set A)
Function remove is similar to filter but remove removes the elements which match the predicate.

Examples:

  > (set->list (remove (λ: ([x : Integer]) (> x 5))
                       (set < 1 2 3 4 5 6)))

  - : (Listof Positive-Fixnum)

  '(1 2 3 4 5)

  > (set->list (remove (λ: ([x : Integer]) (< x 5))
                       (set < 1 2 3 4 5 6)))

  - : (Listof Positive-Fixnum)

  '(5 6)

  > (set->list (remove (λ: ([x : Integer]) (<= x 5))
                       (set < 1 2 3 4 5 6)))

  - : (Listof Positive-Fixnum)

  '(6)

  ← prev  up  next →