HashMap, HashSet & Trie

HashMap, HashSet, and Trie are persistent immutable collections. Every update returns a brand-new collection that shares most of its structure with the old one, so the original is never mutated and copies are cheap.

The defining feature of HashMap and HashSet is that keys/values are compared with Effect’s Equal and Hash traits, not by reference. Two structurally-equal objects (for example two Data.struct values or two branded ids with the same contents) collide as the same key — unlike a native Map/Set, which key by object identity. Trie is the special case where keys are always string, which unlocks fast prefix queries.

import { Data, HashMap } from "effect"

// A value-equal key: two structurally identical Data.struct values are equal
const k1 = Data.struct({ org: "acme", repo: "core" })
const k2 = Data.struct({ org: "acme", repo: "core" })

const stars = HashMap.empty<typeof k1, number>().pipe(
  HashMap.set(k1, 42)
)

console.log(HashMap.get(stars, k2)) // => Option.some(42)  -- k2 finds k1's entry

// A native Map keys by reference, so k2 would NOT find k1:
const native = new Map([[k1, 42]])
console.log(native.get(k2)) // => undefined

Because lookups are value-based, missing keys are explicit: get returns an Option, never undefined.

Batched updates

Each set/remove/add allocates a new collection. When you apply many updates in a row, that intermediate allocation is wasted. HashMap (and HashSet internally) supports a mutation window: beginMutation returns a transient draft you can mutate in place, and endMutation seals it back into an immutable value. The mutate helper wraps both for you.

import { HashMap } from "effect"

const base = HashMap.make(["a", 1])

// mutate: one transient draft, sealed automatically — no per-step allocations
const result = HashMap.mutate(base, (draft) => {
  HashMap.set(draft, "b", 2)
  HashMap.set(draft, "c", 3)
  HashMap.remove(draft, "a")
})

console.log(HashMap.size(result)) // => 2
console.log(HashMap.size(base)) // => 1  -- original untouched

// The explicit form is equivalent:
const draft = HashMap.beginMutation(base)
HashMap.set(draft, "b", 2)
HashMap.set(draft, "c", 3)
const sealed = HashMap.endMutation(draft)
console.log(HashMap.size(sealed)) // => 2

Caution

Only use the draft returned by beginMutation within the mutation window, and treat the value returned by endMutation (or mutate) as the real result. Do not keep using the original after handing it to beginMutation.

Prefix queries with Trie

A Trie<V> is a string-keyed map stored as a prefix tree, so it can answer “which entries start with this string?” in time proportional to the prefix length — ideal for autocomplete, command tables, and routing. Iteration is in alphabetical key order, not insertion order.

import { Trie } from "effect"

const commands = Trie.make(
  ["commit", "Record changes"],
  ["checkout", "Switch branches"],
  ["clone", "Copy a repository"],
  ["config", "Get and set options"]
)

// Autocomplete: every command starting with "co" (alphabetical by key)
console.log(Trie.toEntriesWithPrefix(commands, "co"))
// => [["commit", "Record changes"], ["config", "Get and set options"]]

console.log(Array.from(Trie.keysWithPrefix(commands, "c")))
// => ["checkout", "clone", "commit", "config"]

---

HashMap

A HashMap<Key, Value> is an immutable key-value map backed by a Hash Array Mapped Trie. Keys are grouped by Hash and matched with Equal. Every operation below that “changes” the map returns a new instance.

import { HashMap } from "effect"

interface HashMap

HashMap<Key, Value> is Iterable<[Key, Value]> and implements Equal, Pipeable, and Inspectable. The namespace also exposes type-level helpers HashMap.HashMap.Key, HashMap.HashMap.Value, and HashMap.HashMap.Entry.

const inventory = HashMap.make(["laptop", { qty: 5 }])
type Id = HashMap.HashMap.Key<typeof inventory> // => string
type Item = HashMap.HashMap.Value<typeof inventory> // => { qty: number }

isHashMap

Type guard: checks whether a value is a HashMap.

console.log(HashMap.isHashMap(HashMap.make(["a", 1]))) // => true
console.log(HashMap.isHashMap({ a: 1 })) // => false

isEmpty

Returns true when the map has no entries.

console.log(HashMap.isEmpty(HashMap.empty())) // => true
console.log(HashMap.isEmpty(HashMap.make(["a", 1]))) // => false

empty

Creates a new empty HashMap.

const map = HashMap.empty<string, number>()
console.log(HashMap.size(map)) // => 0

make

Builds a HashMap from a variadic list of [key, value] pairs.

const map = HashMap.make(["a", 1], ["b", 2], ["c", 3])
console.log(HashMap.size(map)) // => 3

fromIterable

Builds a HashMap from any iterable of [key, value] pairs.

const map = HashMap.fromIterable([["a", 1], ["b", 2]])
console.log(HashMap.get(map, "a")) // => Option.some(1)

get

Looks up a key, returning Option<Value> (none if absent).

const map = HashMap.make(["a", 1])
console.log(HashMap.get(map, "a")) // => Option.some(1)
console.log(HashMap.get(map, "z")) // => Option.none()

getHash

Like get, but you supply a precomputed hash for the key — useful in hot paths where the hash is cached.

import { Hash } from "effect"

const map = HashMap.make(["user1", "Alice"])
console.log(HashMap.getHash(map, "user1", Hash.string("user1"))) // => Option.some("Alice")

getUnsafe

Returns the value directly, throwing if the key is absent. Prefer get unless presence is guaranteed.

const config = HashMap.make(["url", "https://example.com"])
console.log(HashMap.getUnsafe(config, "url")) // => "https://example.com"
// HashMap.getUnsafe(config, "missing") // throws "HashMap.getUnsafe: key not found"

has

Checks whether a key has an entry.

const map = HashMap.make(["a", 1])
console.log(HashMap.has(map, "a")) // => true
console.log(HashMap.has(map, "z")) // => false

hasHash

Like has, using a precomputed hash. A matching hash still does not override key equality.

import { Hash } from "effect"

const map = HashMap.make(["Admin", { role: "admin" }])
console.log(HashMap.hasHash(map, "Admin", Hash.string("Admin"))) // => true

hasBy

Checks whether any entry matches a (value, key) predicate.

const map = HashMap.make([1, "a"], [2, "b"])
console.log(HashMap.hasBy(map, (value, key) => key === 1 && value === "a")) // => true
console.log(HashMap.hasBy(map, (value) => value === "z")) // => false

keys

Returns an IterableIterator of keys (hash order — sort if you need determinism).

const map = HashMap.make(["a", 1], ["b", 2])
console.log(Array.from(HashMap.keys(map)).sort()) // => ["a", "b"]

values

Returns an IterableIterator of values.

const map = HashMap.make(["a", 1], ["b", 2])
console.log(Array.from(HashMap.values(map)).sort()) // => [1, 2]

toValues

Returns the values as an Array (eager Array.from(values(self))).

const map = HashMap.make(["a", 1], ["b", 2])
console.log(HashMap.toValues(map).sort()) // => [1, 2]

entries

Returns an IterableIterator of [key, value] entries.

const map = HashMap.make(["a", 1])
console.log(Array.from(HashMap.entries(map))) // => [["a", 1]]

toEntries

Returns the entries as an Array<[key, value]>.

const map = HashMap.make(["a", 1], ["b", 2])
console.log(HashMap.toEntries(map).sort()) // => [["a", 1], ["b", 2]]

size

Returns the number of entries.

console.log(HashMap.size(HashMap.make(["a", 1], ["b", 2]))) // => 2

set

Sets a key to a value, returning a new map.

const map = HashMap.make(["a", 1])
console.log(HashMap.get(HashMap.set(map, "b", 2), "b")) // => Option.some(2)

setMany

Sets many [key, value] pairs at once; later duplicate keys win.

const map = HashMap.make(["a", 1])
const next = HashMap.setMany(map, [["b", 2], ["a", 10]])
console.log(HashMap.get(next, "a")) // => Option.some(10)

remove

Removes a key, returning a new map.

const map = HashMap.make(["a", 1], ["b", 2])
console.log(HashMap.has(HashMap.remove(map, "a"), "a")) // => false

removeMany

Removes all of the given keys.

const map = HashMap.make(["a", 1], ["b", 2], ["c", 3])
console.log(HashMap.size(HashMap.removeMany(map, ["a", "c"]))) // => 1

modify

Updates an existing key’s value with (v) => v; a no-op if the key is absent.

const map = HashMap.make(["a", 1])
console.log(HashMap.get(HashMap.modify(map, "a", (v) => v * 3), "a")) // => Option.some(3)

modifyAt

Inserts, updates, or removes a key using an Option => Option function: receives some(value) if present (else none); return some to store, none to remove.

import { Option } from "effect"

const map = HashMap.make(["a", 1])
const inc = (o: Option.Option<number>) =>
  Option.isSome(o) ? Option.some(o.value + 1) : Option.some(1)
console.log(HashMap.get(HashMap.modifyAt(map, "a", inc), "a")) // => Option.some(2)
console.log(HashMap.get(HashMap.modifyAt(map, "b", inc), "b")) // => Option.some(1)

modifyHash

Like modifyAt, but with a precomputed hash.

import { Hash, Option } from "effect"

const map = HashMap.make(["hits", 100])
const inc = (o: Option.Option<number>) =>
  Option.isSome(o) ? Option.some(o.value + 1) : Option.some(1)
console.log(
  HashMap.get(HashMap.modifyHash(map, "hits", Hash.string("hits"), inc), "hits")
) // => Option.some(101)

union

Combines two maps; on equal keys the value from that (the second map) wins.

const a = HashMap.make(["a", 1], ["b", 2])
const b = HashMap.make(["b", 20], ["c", 3])
console.log(HashMap.get(HashMap.union(a, b), "b")) // => Option.some(20)

beginMutation

Returns a transient mutable draft for batched updates. Pair with endMutation.

const draft = HashMap.beginMutation(HashMap.make(["a", 1]))
HashMap.set(draft, "b", 2)
console.log(HashMap.size(HashMap.endMutation(draft))) // => 2

endMutation

Seals a draft from beginMutation back into an immutable HashMap.

const draft = HashMap.beginMutation(HashMap.empty<string, number>())
HashMap.set(draft, "x", 1)
const final = HashMap.endMutation(draft)
console.log(HashMap.size(final)) // => 1

mutate

Runs a callback against a transient draft and returns the sealed result — the ergonomic form of beginMutation/endMutation.

const result = HashMap.mutate(HashMap.make(["a", 1]), (draft) => {
  HashMap.set(draft, "b", 2)
  HashMap.set(draft, "c", 3)
})
console.log(HashMap.size(result)) // => 3

map

Transforms every value via (value, key) => newValue, returning a new map.

const map = HashMap.make(["a", 1], ["b", 2])
const out = HashMap.map(map, (value, key) => `${key}:${value * 2}`)
console.log(HashMap.get(out, "a")) // => Option.some("a:2")

flatMap

Maps each entry to a HashMap and merges the results (both maps must share equality/hash behavior).

const map = HashMap.make(["a", 1])
const out = HashMap.flatMap(map, (value, key) =>
  HashMap.make([key + "1", value], [key + "2", value * 2])
)
console.log(HashMap.get(out, "a2")) // => Option.some(2)

forEach

Runs a (value, key) => void side effect for each entry.

const collected: Array<string> = []
HashMap.forEach(HashMap.make(["a", 1], ["b", 2]), (v, k) => collected.push(`${k}=${v}`))
console.log(collected.sort()) // => ["a=1", "b=2"]

reduce

Folds the entries into a single value via (acc, value, key) => acc.

const map = HashMap.make(["a", 1], ["b", 2], ["c", 3])
console.log(HashMap.reduce(map, 0, (acc, value) => acc + value)) // => 6

filter

Keeps only entries matching a (value, key) predicate.

const map = HashMap.make(["a", 1], ["b", 2], ["c", 3])
console.log(HashMap.size(HashMap.filter(map, (v) => v % 2 === 1))) // => 2

filterMap

Maps and filters in one pass: return Result.succeed to keep, Result.failVoid to drop.

import { Result } from "effect"

const map = HashMap.make(["a", 1], ["b", 2], ["c", 3])
const evens = HashMap.filterMap(map, (v) =>
  v % 2 === 0 ? Result.succeed(v * 10) : Result.failVoid
)
console.log(HashMap.get(evens, "b")) // => Option.some(20)

compact

Drops Option.none values from a HashMap of Options, unwrapping the rest.

import { Option } from "effect"

const map = HashMap.make(["a", Option.some(1)], ["b", Option.none<number>()])
console.log(HashMap.size(HashMap.compact(map))) // => 1

findFirst

Returns the first [key, value] matching a predicate as an Option.

const map = HashMap.make(["a", 1], ["b", 2])
console.log(HashMap.findFirst(map, (v, k) => k === "b")) // => Option.some(["b", 2])

some

Returns true if any entry matches the predicate.

const map = HashMap.make(["a", 1], ["b", 2])
console.log(HashMap.some(map, (v) => v > 1)) // => true

every

Returns true if all entries match the predicate.

const map = HashMap.make(["a", 1], ["b", 2])
console.log(HashMap.every(map, (v) => v > 0)) // => true

---

HashSet

A HashSet<A> is an immutable set of unique values, deduplicated by Equal/Hash (it is backed by a HashMap internally). All combinators return new sets.

import { HashSet } from "effect"

interface HashSet

HashSet<Value> is Iterable<Value> and implements Equal, Pipeable, and Inspectable. The type-level helper HashSet.HashSet.Value extracts the element type.

const fruits = HashSet.make("apple", "banana")
type Fruit = HashSet.HashSet.Value<typeof fruits> // => string

isHashSet

Type guard: checks whether a value is a HashSet.

console.log(HashSet.isHashSet(HashSet.make(1, 2))) // => true
console.log(HashSet.isHashSet([1, 2])) // => false

empty

Creates an empty HashSet.

console.log(HashSet.size(HashSet.empty<string>())) // => 0

make

Builds a set from a variadic list of values; duplicates collapse.

console.log(HashSet.size(HashSet.make(1, 2, 2, 3))) // => 3

fromIterable

Builds a set from any iterable; duplicates collapse.

console.log(HashSet.size(HashSet.fromIterable(["a", "b", "a"]))) // => 2

add

Adds a value, returning a new set (no-op if already present).

const set = HashSet.make("a")
console.log(HashSet.has(HashSet.add(set, "b"), "b")) // => true

has

Checks membership using Equal/Hash.

const set = HashSet.make("apple", "banana")
console.log(HashSet.has(set, "apple")) // => true
console.log(HashSet.has(set, "grape")) // => false

remove

Removes a value, returning a new set (no-op if absent).

const set = HashSet.make("a", "b")
console.log(HashSet.has(HashSet.remove(set, "a"), "a")) // => false

size

Returns the number of values.

console.log(HashSet.size(HashSet.make("a", "b", "c"))) // => 3

isEmpty

Returns true when the set has no values.

console.log(HashSet.isEmpty(HashSet.empty())) // => true
console.log(HashSet.isEmpty(HashSet.make("a"))) // => false

union

Returns all values in either set.

const a = HashSet.make("a", "b")
const b = HashSet.make("b", "c")
console.log(Array.from(HashSet.union(a, b)).sort()) // => ["a", "b", "c"]

intersection

Returns only values present in both sets.

const a = HashSet.make("a", "b", "c")
const b = HashSet.make("b", "c", "d")
console.log(Array.from(HashSet.intersection(a, b)).sort()) // => ["b", "c"]

difference

Returns values in the first set that are not in the second.

const a = HashSet.make("a", "b", "c")
const b = HashSet.make("b", "d")
console.log(Array.from(HashSet.difference(a, b)).sort()) // => ["a", "c"]

isSubset

Returns true if every value of the first set is in the second.

const small = HashSet.make("a", "b")
const large = HashSet.make("a", "b", "c")
console.log(HashSet.isSubset(small, large)) // => true
console.log(HashSet.isSubset(large, small)) // => false

map

Maps each value; the result may be smaller if values collide.

const set = HashSet.make("apple", "banana", "cherry")
console.log(Array.from(HashSet.map(set, (s) => s.length)).sort()) // => [5, 6]

filter

Keeps only values matching the predicate (supports refinements).

const set = HashSet.make(1, 2, 3, 4)
console.log(Array.from(HashSet.filter(set, (n) => n % 2 === 0)).sort()) // => [2, 4]

reduce

Folds the values into a single result.

const set = HashSet.make(1, 2, 3, 4)
console.log(HashSet.reduce(set, 0, (acc, n) => acc + n)) // => 10

some

Returns true if any value matches the predicate.

console.log(HashSet.some(HashSet.make(1, 2, 3), (n) => n > 2)) // => true

every

Returns true if all values match the predicate (vacuously true when empty).

console.log(HashSet.every(HashSet.make(2, 4, 6), (n) => n % 2 === 0)) // => true

---

Trie

A Trie<Value> is an immutable string-keyed map stored as a prefix tree. Iteration and the keys/values/entries getters yield results in alphabetical key order, regardless of insertion order. Lookups cost is proportional to key length, and prefix queries are the headline feature.

import { Trie } from "effect"

interface Trie

Trie<Value> is Iterable<[string, Value]> and implements Equal, Pipeable, and Inspectable. Updates such as insert and remove return new tries.

const trie = Trie.make(["app", 1], ["apple", 2])
for (const [key, value] of trie) console.log(key, value)
// => "app 1" then "apple 2"

empty

Creates an empty Trie.

console.log(Trie.size(Trie.empty<number>())) // => 0

make

Builds a Trie from a variadic list of [string, value] entries.

const trie = Trie.make(["ca", 0], ["me", 1])
console.log(Trie.toEntries(trie)) // => [["ca", 0], ["me", 1]]

fromIterable

Builds a Trie from any iterable of [string, value] entries.

const trie = Trie.fromIterable([["mind", 2], ["call", 0]])
console.log(Trie.toEntries(trie)) // => [["call", 0], ["mind", 2]]

insert

Inserts (or overwrites) one entry, returning a new Trie.

const trie = Trie.empty<number>().pipe(Trie.insert("call", 0))
console.log(Trie.get(trie, "call")) // => Option.some(0)

insertMany

Inserts multiple entries at once.

const trie = Trie.empty<number>().pipe(Trie.insertMany([["she", 0], ["sea", 1]]))
console.log(Trie.size(trie)) // => 2

get

Looks up an exact key, returning Option<Value>.

const trie = Trie.make(["call", 0])
console.log(Trie.get(trie, "call")) // => Option.some(0)
console.log(Trie.get(trie, "ca")) // => Option.none()

getUnsafe

Returns the value directly, throwing if the key is absent. Prefer get.

const trie = Trie.make(["call", 0])
console.log(Trie.getUnsafe(trie, "call")) // => 0
// Trie.getUnsafe(trie, "ca") // throws

has

Checks whether an exact key exists.

const trie = Trie.make(["call", 0])
console.log(Trie.has(trie, "call")) // => true
console.log(Trie.has(trie, "ca")) // => false

size

Returns the number of entries.

console.log(Trie.size(Trie.make(["a", 0], ["b", 1]))) // => 2

isEmpty

Returns true when the trie has no entries.

console.log(Trie.isEmpty(Trie.empty())) // => true
console.log(Trie.isEmpty(Trie.make(["a", 0]))) // => false

longestPrefixOf

Returns the longest stored key that is a prefix of the given key, with its value, as an Option<[string, Value]>.

const trie = Trie.make(["shells", 0], ["sells", 1], ["she", 2])
console.log(Trie.longestPrefixOf(trie, "sells")) // => Option.some(["sells", 1])
console.log(Trie.longestPrefixOf(trie, "sell")) // => Option.none()

keys

Returns an IterableIterator of all keys in alphabetical order.

const trie = Trie.make(["cab", 0], ["abc", 1], ["bca", 2])
console.log(Array.from(Trie.keys(trie))) // => ["abc", "bca", "cab"]

values

Returns an IterableIterator of all values, ordered by their keys.

const trie = Trie.make(["call", 0], ["me", 1], ["and", 2])
console.log(Array.from(Trie.values(trie))) // => [2, 0, 1]  (and, call, me)

entries

Returns an IterableIterator of [key, value] entries in key order.

const trie = Trie.make(["me", 1], ["call", 0])
console.log(Array.from(Trie.entries(trie))) // => [["call", 0], ["me", 1]]

toEntries

Returns all entries as an Array<[string, Value]> (eager).

const trie = Trie.make(["call", 0], ["me", 1])
console.log(Trie.toEntries(trie)) // => [["call", 0], ["me", 1]]

keysWithPrefix

Returns the keys (in order) that start with prefix, including prefix itself if present.

const trie = Trie.make(["she", 0], ["shells", 1], ["sea", 2], ["shore", 3])
console.log(Array.from(Trie.keysWithPrefix(trie, "she"))) // => ["she", "shells"]

valuesWithPrefix

Returns the values whose keys start with prefix.

const trie = Trie.make(["she", 0], ["shells", 1], ["sea", 2])
console.log(Array.from(Trie.valuesWithPrefix(trie, "she"))) // => [0, 1]

entriesWithPrefix

Returns the [key, value] entries whose keys start with prefix.

const trie = Trie.make(["she", 0], ["shells", 1], ["sea", 2])
console.log(Array.from(Trie.entriesWithPrefix(trie, "she"))) // => [["she", 0], ["shells", 1]]

toEntriesWithPrefix

Returns the prefixed [key, value] entries as an Array (eager).

const trie = Trie.make(["shells", 0], ["sells", 1], ["sea", 2], ["she", 3])
console.log(Trie.toEntriesWithPrefix(trie, "she")) // => [["she", 3], ["shells", 0]]

remove

Removes the entry for a key, returning a new Trie (no-op if absent).

const trie = Trie.make(["call", 0], ["me", 1])
console.log(Trie.get(Trie.remove(trie, "call"), "call")) // => Option.none()

removeMany

Removes all entries for the given keys.

const trie = Trie.make(["shells", 0], ["sells", 1], ["she", 2])
console.log(Trie.toEntries(Trie.removeMany(trie, ["she", "sells"]))) // => [["shells", 0]]

modify

Updates an existing key’s value via (v) => v; a no-op if the key is absent.

const trie = Trie.make(["she", 2])
console.log(Trie.get(Trie.modify(trie, "she", (v) => v + 10), "she")) // => Option.some(12)

map

Transforms every value via (value, key) => newValue, returning a new Trie.

const trie = Trie.make(["shells", 0], ["she", 2])
console.log(Trie.toEntries(Trie.map(trie, (v) => v + 1))) // => [["she", 3], ["shells", 1]]

filter

Keeps only entries matching a (value, key) predicate (supports refinements).

const trie = Trie.make(["shells", 0], ["sells", 1], ["she", 2])
console.log(Trie.toEntries(Trie.filter(trie, (v) => v > 1))) // => [["she", 2]]

filterMap

Maps and filters in one pass: Result.succeed keeps, Result.failVoid drops.

import { Result } from "effect"

const trie = Trie.make(["shells", 0], ["sells", 1], ["she", 2])
const kept = Trie.filterMap(trie, (v) =>
  v > 1 ? Result.succeed(v) : Result.failVoid
)
console.log(Trie.toEntries(kept)) // => [["she", 2]]

compact

Drops Option.none values from a Trie of Options, unwrapping the rest.

import { Option } from "effect"

const trie = Trie.make(
  ["shells", Option.some(0)],
  ["sells", Option.none<number>()],
  ["she", Option.some(2)]
)
console.log(Trie.toEntries(Trie.compact(trie))) // => [["she", 2], ["shells", 0]]

reduce

Folds the entries into a single value via (acc, value, key) => acc, in key order.

const trie = Trie.make(["shells", 0], ["sells", 1], ["she", 2])
console.log(Trie.reduce(trie, 0, (acc, v) => acc + v)) // => 3
console.log(Trie.reduce(trie, "", (acc, _, key) => acc + key)) // => "sellssheshells"

forEach

Runs a (value, key) => void side effect for each entry in key order.

let total = 0
Trie.forEach(Trie.make(["she", 2], ["sells", 1]), (n, key) => {
  total += n + key.length
})
console.log(total) // => 11  (she: 2+3, sells: 1+5)