HashSet.ts overview

HashSet

An immutable HashSet provides a collection of unique values with efficient lookup, insertion and removal. Once created, a HashSet cannot be modified; any operation that would alter the set instead returns a new HashSet with the changes. This immutability offers benefits like predictable state management and easier reasoning about your code.

What Problem Does It Solve?

HashSet solves the problem of maintaining an unsorted collection where each value appears exactly once, with fast operations for checking membership and adding/removing values.

When to Use

Use HashSet when you need:

A collection with no duplicate values
Efficient membership testing (O(1) average complexity)
Set operations like union, intersection, and difference
An immutable data structure that preserves functional programming patterns

Advanced Features

HashSet provides operations for:

Transforming sets with map and flatMap
Filtering elements with filter
Combining sets with union, intersection and difference
Performance optimizations via mutable operations in controlled contexts

Performance Characteristics

Lookup operations (module:HashSet.has): O(1) average time complexity
Insertion operations (module:HashSet.add): O(1) average time complexity
Removal operations (module:HashSet.remove): O(1) average time complexity
Set operations (module:HashSet.union, module:HashSet.intersection): O(n) where n is the size of the smaller set
Iteration: O(n) where n is the size of the set

The HashSet data structure implements the following traits:

Iterable: allows iterating over the values in the set
Equal: allows comparing two sets for value-based equality
Pipeable: allows chaining operations with the pipe operator
Inspectable: allows inspecting the contents of the set

Operations Reference

Category	Operation	Description	Complexity
constructors	`module:HashSet.empty`	Creates an empty HashSet	O(1)
constructors	`module:HashSet.fromIterable`	Creates a HashSet from an iterable	O(n)
constructors	`module:HashSet.make`	Creates a HashSet from multiple values	O(n)

elements	`module:HashSet.has`	Checks if a value exists in the set	O(1) avg
elements	`module:HashSet.some`	Checks if any element satisfies a predicate	O(n)
elements	`module:HashSet.every`	Checks if all elements satisfy a predicate	O(n)
elements	`module:HashSet.isSubset`	Checks if a set is a subset of another	O(n)

getters	`module:HashSet.values`	Gets an iterator of all values	O(1)
getters	`module:HashSet.toValues`	Gets an array of all values	O(n)
getters	`module:HashSet.size`	Gets the number of elements	O(1)

mutations	`module:HashSet.add`	Adds a value to the set	O(1) avg
mutations	`module:HashSet.remove`	Removes a value from the set	O(1) avg
mutations	`module:HashSet.toggle`	Toggles a value’s presence	O(1) avg

operations	`module:HashSet.difference`	Computes set difference (A - B)	O(n)
operations	`module:HashSet.intersection`	Computes set intersection (A ∩ B)	O(n)
operations	`module:HashSet.union`	Computes set union (A ∪ B)	O(n)

mapping	`module:HashSet.map`	Transforms each element	O(n)

sequencing	`module:HashSet.flatMap`	Transforms and flattens elements	O(n)

traversing	`module:HashSet.forEach`	Applies a function to each element	O(n)

folding	`module:HashSet.reduce`	Reduces the set to a single value	O(n)

filtering	`module:HashSet.filter`	Keeps elements that satisfy a predicate	O(n)

partitioning	`module:HashSet.partition`	Splits into two sets by a predicate	O(n)

Notes

Composability with the Effect Ecosystem:

This HashSet is designed to work seamlessly within the Effect ecosystem. It implements the Iterable, Equal, Pipeable, and Inspectable traits from Effect. This ensures compatibility with other Effect data structures and functionalities. For example, you can easily use Effect’s pipe method to chain operations on the HashSet.

Equality of Elements with Effect’s Equal Trait:

This HashSet relies on Effect’s Equal trait to determine the uniqueness of elements within the set. The way equality is checked depends on the type of the elements:

Primitive Values: For primitive JavaScript values like strings, numbers, booleans, null, and undefined, equality is determined by their value (similar to the === operator).
Objects and Custom Types: For objects and other custom types, equality is determined by whether those types implement the Equal interface themselves. If an element type implements Equal, the HashSet will delegate to that implementation to perform the equality check. This allows you to define custom logic for determining when two instances of your objects should be considered equal based on their properties, rather than just their object identity.

import { Equal, Hash, HashSet } from "effect"

class Person implements Equal.Equal {
  constructor(
    readonly id: number, // Unique identifier
    readonly name: string,
    readonly age: number
  ) {}

  // Define equality based on id, name, and age
  [Equal.symbol](that: Equal.Equal): boolean {
    if (that instanceof Person) {
      return Equal.equals(this.id, that.id) && Equal.equals(this.name, that.name) && Equal.equals(this.age, that.age)
    }
    return false
  }

  // Generate a hash code based on the unique id
  [Hash.symbol](): number {
    return Hash.hash(this.id)
  }
}

// Creating a HashSet with objects that implement the Equal interface
const set = HashSet.empty().pipe(HashSet.add(new Person(1, "Alice", 30)), HashSet.add(new Person(1, "Alice", 30)))

// HashSet recognizes them as equal, so only one element is stored
console.log(HashSet.size(set))
// Output: 1

Simplifying Equality and Hashing with Data and Schema:

Effect’s Data and Schema.Data modules offer powerful ways to automatically handle the implementation of both the Equal and Hash traits for your custom data structures.

Data Module: By using constructors like Data.struct, Data.tuple, Data.array, or Data.case to define your data types, Effect automatically generates the necessary implementations for value-based equality and consistent hashing. This significantly reduces boilerplate and ensures correctness.

import { HashSet, Data, Equal } from "effect"
import assert from "node:assert/strict"

// Data.* implements the `Equal` traits for us
const person1 = Data.struct({ id: 1, name: "Alice", age: 30 })
const person2 = Data.struct({ id: 1, name: "Alice", age: 30 })

assert(Equal.equals(person1, person2))

const set = HashSet.empty().pipe(HashSet.add(person1), HashSet.add(person2))

// HashSet recognizes them as equal, so only one element is stored
console.log(HashSet.size(set)) // Output: 1

Schema Module: When defining data schemas using the Schema module, you can use Schema.Data to automatically include the Equal and Hash traits in the decoded objects. This is particularly important when working with HashSet. For decoded objects to be correctly recognized as equal within a HashSet, ensure that the schema for those objects is defined using Schema.Data.

import { Equal, HashSet, Schema } from "effect"
import assert from "node:assert/strict"

// Schema.Data implements the `Equal` traits for us
const PersonSchema = Schema.Data(
  Schema.Struct({
    id: Schema.Number,
    name: Schema.String,
    age: Schema.Number
  })
)

const Person = Schema.decode(PersonSchema)

const person1 = Person({ id: 1, name: "Alice", age: 30 })
const person2 = Person({ id: 1, name: "Alice", age: 30 })

assert(Equal.equals(person1, person2)) // Output: true

const set = HashSet.empty().pipe(HashSet.add(person1), HashSet.add(person2))

// HashSet thanks to Schema.Data implementation of the `Equal` trait, recognizes the two Person as equal, so only one element is stored
console.log(HashSet.size(set)) // Output: 1

Interoperability with the JavaScript Runtime:

To interoperate with the regular JavaScript runtime, Effect’s HashSet provides methods to access its elements in formats readily usable by JavaScript APIs: HashSet.values, HashSet.toValues

import { HashSet } from "effect"

const hashSet: HashSet.HashSet<number> = HashSet.make(1, 2, 3)

// Using HashSet.values to convert HashSet.HashSet<A> to IterableIterator<A>
const iterable: IterableIterator<number> = HashSet.values(hashSet)

console.log(...iterable) // Logs:  1 2 3

// Using HashSet.toValues to convert HashSet.HashSet<A> to Array<A>
const array: Array<number> = HashSet.toValues(hashSet)

console.log(array) // Logs: [ 1, 2, 3 ]

Be mindful of performance implications (both time and space complexity) when frequently converting between Effect’s immutable HashSet and mutable JavaScript data structures, especially for large collections.

Since v2.0.0

Exports Grouped by Category

constructors
- empty
- fromIterable
- make
elements
- every
- has
- isSubset
- some
filtering
- filter
folding
- reduce
getters
- size
- toValues
- values
mapping
- map
models
- HashSet (interface)
partitioning
- partition
refinements
- isHashSet
sequencing
- flatMap
symbol
- TypeId (type alias)
traversing
- forEach
utils
- add
- beginMutation
- difference
- endMutation
- intersection
- mutate
- remove
- toggle
- union

constructors

empty

Creates an empty HashSet.

Time complexity: O(1)

Example

import { HashSet, pipe } from "effect"

console.log(
  pipe(
    // Provide a type argument to create a HashSet of a specific type
    HashSet.empty<number>(),
    HashSet.add(1),
    HashSet.add(1), // Notice the duplicate
    HashSet.add(2),
    HashSet.toValues
  )
) // Output: [1, 2]

See

Other HashSet constructors are module:HashSet.make module:HashSet.fromIterable

Signature

declare const empty: <A = never>() => HashSet<A>

HashSet.ts overview

HashSet

What Problem Does It Solve?

When to Use

Advanced Features

Performance Characteristics

Operations Reference

Notes

Composability with the Effect Ecosystem:

Interoperability with the JavaScript Runtime:

Exports Grouped by Category

constructors

empty

fromIterable

make

elements

every

has

isSubset

some

filtering

filter

folding

reduce

getters

size

toValues

values

mapping

map

models

HashSet (interface)

partitioning

partition

refinements

isHashSet

sequencing

flatMap

symbol

TypeId (type alias)

traversing

forEach

utils

add

beginMutation

difference

endMutation

intersection

mutate

remove

toggle

union