F# sets
last modified May 17, 2025
In this article we will explore sets in F#. Sets are a fundamental data structure in functional programming, providing a way to store unique elements and perform set operations.
Sets in F# are immutable collections that contain no duplicate elements. They provide efficient lookup operations and support common set operations like union, intersection, and difference. F# sets are implemented as immutable balanced binary trees, which makes them efficient for functional programming patterns.
Since sets in F# are immutable, any operation that modifies a set—such as adding or removing elements—returns a new set instead of altering the original. This ensures that data integrity is preserved and allows for safe concurrent programming. Additionally, the underlying balanced tree structure ensures that set operations, such as membership tests and iteration, remain performant even with large data sets.
Creating sets
There are several ways to create sets in F#. You can create them from sequences,
lists, arrays, or by using set comprehensions. The Set module
provides functions for working with sets.
// Creating empty set
let emptySet = Set.empty
printfn "Empty set: %A" emptySet
// Using set literal
let uniqeueVals = set [ 1; 2; 3; 4; 5 ]
printfn "Unique values: %A" uniqeueVals
// Creating set from list
let numbers = Set.ofList [ 1; 2; 3; 2; 1 ]
printfn "From list: %A" numbers
// Creating set from array
let colors =
Set.ofArray [| "red"
"green"
"blue"
"green" |]
printfn "From array: %A" colors
// Helper function to check if a number is prime
let isPrime n =
if n < 2 then
false
else
seq { 2 .. int (sqrt (float n)) }
|> Seq.forall (fun x -> n % x <> 0)
// Creating set from sequence
let primes =
Set.ofSeq (
seq {
for i in 1..10 do
if isPrime i then yield i
}
)
printfn "Primes: %A" primes
// Set comprehension
let squares = Set.ofSeq (seq { for x in 1..5 -> x * x })
printfn "Squares: %A" squares
This example demonstrates different ways to create sets. Note how duplicates are
automatically removed. The Set.empty function creates an empty set.
The set function creates a set from a list, while the
ofSeq function allows you to create sets from any sequence,
including arrays and lists. The isPrime function is a helper
function to check if a number is prime.
λ dotnet fsi creating_sets.fsx Empty set: set [] Unique values: set [1; 2; 3; 4; 5] From list: set [1; 2; 3] From array: set ["blue"; "green"; "red"] Primes: set [2; 3; 5; 7] Squares: set [1; 4; 9; 16; 25]
Basic set operations
F# sets support fundamental operations like adding elements, checking for membership, and counting elements. Since sets are immutable, operations that modify a set return a new set rather than changing the original.
let mySet = set [1; 2; 3; 4; 5] // Adding elements let biggerSet = mySet.Add(6).Add(7) printfn "After adding: %A" biggerSet // Removing elements let smallerSet = mySet.Remove(5).Remove(1) printfn "After removing: %A" smallerSet // Checking membership printfn "Contains 3? %b" (mySet.Contains 3) printfn "Contains 8? %b" (mySet.Contains 8) // Counting elements printfn "Count: %d" mySet.Count // Minimum and maximum printfn "Min: %d" (Set.minElement mySet) printfn "Max: %d" (Set.maxElement mySet)
This code shows basic set operations. Add and Remove
return new sets. Contains checks for membership, and
Count returns the number of elements. minElement and
maxElement return the smallest and largest elements.
λ dotnet fsi basic_operations.fsx After adding: set [1; 2; 3; 4; 5; 6; 7] After removing: set [2; 3; 4] Contains 3? true Contains 8? false Count: 5 Min: 1 Max: 5
Set operations: union, intersection, difference
F# sets support mathematical set operations including union, intersection, and
difference. These operations are performed using functions from the
Set module or equivalent operators.
let setA = set [1; 2; 3; 4; 5] let setB = set [4; 5; 6; 7; 8] // Union (elements in either set) let unionAB = Set.union setA setB printfn "Union: %A" unionAB // Alternative union syntax let unionAB2 = setA + setB printfn "Union with +: %A" unionAB2 // Intersection (elements in both sets) let intersectAB = Set.intersect setA setB printfn "Intersection: %A" intersectAB // Difference (elements in first set but not second) let diffAB = Set.difference setA setB printfn "Difference A-B: %A" diffAB // Symmetric difference (elements in either set but not both) let symDiffAB = (setA - setB) + (setB - setA) printfn "Symmetric difference: %A" symDiffAB
This example demonstrates fundamental set operations. The +
operator can be used for union, while - is used for difference.
Note that symmetric difference isn't built-in but can be constructed from other
operations.
λ dotnet fsi set_operations.fsx Union: set [1; 2; 3; 4; 5; 6; 7; 8] Union with +: set [1; 2; 3; 4; 5; 6; 7; 8] Intersection: set [4; 5] Difference A-B: set [1; 2; 3] Symmetric difference: set [1; 2; 3; 6; 7; 8]
Set comparisons and subset operations
Sets can be compared for equality and subset relationships. F# provides functions to check if one set is a subset or superset of another, or if they contain exactly the same elements.
let setX = set [1; 2; 3; 4] let setY = set [3; 4; 5; 6] let setZ = set [3; 4] // Equality printfn "X equals Y? %b" (setX = setY) printfn "X equals X? %b" (setX = setX) // Subset checks printfn "Z subset of X? %b" (Set.isSubset setZ setX) printfn "Z proper subset of X? %b" (Set.isProperSubset setZ setX) printfn "Z subset of Y? %b" (Set.isSubset setZ setY) // Superset checks printfn "X superset of Z? %b" (Set.isSuperset setX setZ) printfn "Y superset of Z? %b" (Set.isSuperset setY setZ)
The example shows how to compare sets. isSubset checks if all
elements of one set are in another, while isProperSubset requires
the sets to be different. isSuperset is the inverse of
isSubset.
λ dotnet fsi set_comparisons.fsx X equals Y? false X equals X? true Z subset of X? true Z proper subset of X? true Z subset of Y? true X superset of Z? true Y superset of Z? true
Set transformations and filtering
Sets can be transformed and filtered using higher-order functions like
map and filter. These operations return new sets with
the transformed or filtered elements.
let numbers = set [1; 2; 3; 4; 5; 6; 7; 8; 9; 10] // Mapping a function over a set let squares = Set.map (fun x -> x * x) numbers printfn "Squares: %A" squares // Filtering elements let evens = Set.filter (fun x -> x % 2 = 0) numbers printfn "Evens: %A" evens // Folding (reducing) a set let sum = Set.fold (fun acc x -> acc + x) 0 numbers printfn "Sum: %d" sum // Iterating over a set printf "Elements: " Set.iter (fun x -> printf "%d " x) numbers printfn ""
This code demonstrates functional transformations on sets. map
applies a function to each element, filter selects elements
matching a predicate, fold reduces the set to a single value, and
iter performs an action for each element.
λ dotnet fsi set_transformations.fsx Squares: set [1; 4; 9; 16; 25; 36; 49; 64; 81; 100] Evens: set [2; 4; 6; 8; 10] Sum: 55 Elements: 1 2 3 4 5 6 7 8 9 10
Working with custom types
Sets can contain custom types, but the types must support comparison. For records and discriminated unions, F# automatically generates comparison implementations if all constituent types support comparison.
type Person = {
Name: string
Age: int
}
let people = set [
{ Name = "Alice"; Age = 30 }
{ Name = "Bob"; Age = 25 }
{ Name = "Alice"; Age = 30 } // Duplicate
{ Name = "Charlie"; Age = 35 }
]
printfn "People set: %A" people
printfn "Count: %d" people.Count
type Shape =
| Circle of radius: float
| Rectangle of width: float * height: float
let shapes = set [
Circle 2.5
Rectangle (3.0, 4.0)
Circle 2.5 // Duplicate
Rectangle (1.0, 2.0)
]
printfn "Shapes set: %A" shapes
printfn "Contains Circle 2.5? %b" (shapes.Contains (Circle 2.5))
This example shows sets containing custom types. The Person record
and Shape discriminated union automatically support comparison, so
they can be used in sets. Duplicates are automatically removed based on the
comparison.
λ dotnet fsi custom_types.fsx
People set: set [{ Name = "Alice"
Age = 30; }; { Name = "Bob"
Age = 25; }; { Name = "Charlie"
Age = 35; }]
Count: 3
Shapes set: set [Circle 2.5; Rectangle (1.0, 2.0); Rectangle (3.0, 4.0)]
Contains Circle 2.5? true
F# sets are powerful immutable collections that provide efficient lookup operations and support mathematical set operations. Their immutable nature makes them ideal for functional programming patterns, and their implementation as balanced binary trees ensures good performance. Whether you need to work with unique collections of data or perform set-theoretic operations, F# sets offer a robust solution.