1/**
2 * Stores string-keyed values in an immutable prefix tree.
3 *
4 * A `Trie<Value>` is similar to a map whose keys are strings, but it is built
5 * for looking up keys by prefix. It is useful for autocomplete, route tables,
6 * dictionaries, and command lookup. Updates return new tries, and the module
7 * includes exact lookup, prefix lookup, longest-prefix lookup, iteration,
8 * mapping, filtering, reducing, and traversal helpers.
9 *
10 * @since 2.0.0
11 */
12import type { Equal } from "./Equal.ts"
13import type { Inspectable } from "./Inspectable.ts"
14import * as TR from "./internal/trie.ts"
15import type { Option } from "./Option.ts"
16import type { Pipeable } from "./Pipeable.ts"
17import type { Result } from "./Result.ts"
18import type { Covariant, NoInfer } from "./Types.ts"
19
20const TypeId = TR.TrieTypeId
21
22/**
23 * An immutable string-keyed map optimized for prefix lookup. Iteration yields
24 * `[key, value]` pairs in key order, and update operations such as insert and
25 * remove return new `Trie` values.
26 *
27 * **Example** (Using a trie for prefix search)
28 *
29 * ```ts import.meta.vitest
30 * import { Option, Trie } from "effect"
31 *
32 * // Create a trie with string-to-number mappings
33 * const trie: Trie.Trie<number> = Trie.make(
34 * ["apple", 1],
35 * ["app", 2],
36 * ["application", 3],
37 * ["banana", 4]
38 * )
39 *
40 * // Get values by exact key
41 * Trie.get(trie, "apple") // => Option.some(1)
42 * Trie.get(trie, "grape") // => Option.none()
43 *
44 * // Find all keys with a prefix
45 * Array.from(Trie.keysWithPrefix(trie, "app")) // => ["app", "apple", "application"]
46 *
47 * // Iterate over all entries (sorted alphabetically)
48 * Array.from(trie) // => [["app", 2], ["apple", 1], ["application", 3], ["banana", 4]]
49 *
50 * // Check if key exists
51 * Trie.has(trie, "app") // => true
52 *
53 * // Get size
54 * Trie.size(trie) // => 4
55 * ```
56 *
57 * @category models
58 * @since 2.0.0
59 */
60export interface Trie<in out Value> extends Iterable<[string, Value]>, Equal, Pipeable, Inspectable {
61 readonly [TypeId]: {
62 readonly _Value: Covariant<Value>
63 }
64}
65
66/**
67 * Creates an empty `Trie`.
68 *
69 * **Example** (Creating an empty trie)
70 *
71 * ```ts import.meta.vitest
72 * import { Trie } from "effect"
73 *
74 * const trie = Trie.empty<string>()
75 *
76 * Trie.size(trie) // => 0
77 * Array.from(trie) // => []
78 * ```
79 *
80 * @category constructors
81 * @since 2.0.0
82 */
83export const empty: <V = never>() => Trie<V> = TR.empty
84
85/**
86 * Creates a new `Trie` from an iterable collection of key/value pairs (e.g. `Array<[string, V]>`).
87 *
88 * **Example** (Creating a trie from entries)
89 *
90 * ```ts import.meta.vitest
91 * import { Trie } from "effect"
92 *
93 * const iterable: Array<readonly [string, number]> = [["call", 0], ["me", 1], [
94 * "mind",
95 * 2
96 * ], ["mid", 3]]
97 * const trie = Trie.fromIterable(iterable)
98 *
99 * // The entries in the `Trie` are extracted in alphabetical order, regardless of the insertion order
100 * Array.from(trie) // => [["call", 0], ["me", 1], ["mid", 3], ["mind", 2]]
101 * trie // => Trie.make(["call", 0], ["me", 1], ["mind", 2], ["mid", 3])
102 * ```
103 *
104 * @category constructors
105 * @since 2.0.0
106 */
107export const fromIterable: <V>(entries: Iterable<readonly [string, V]>) => Trie<V> = TR.fromIterable
108
109/**
110 * Constructs a new `Trie` from the specified entries (`[string, V]`).
111 *
112 * **Example** (Constructing a trie from entries)
113 *
114 * ```ts import.meta.vitest
115 * import { Trie } from "effect"
116 *
117 * const trie = Trie.make(["ca", 0], ["me", 1])
118 *
119 * Array.from(trie) // => [["ca", 0], ["me", 1]]
120 * trie // => Trie.fromIterable([["ca", 0], ["me", 1]])
121 * ```
122 *
123 * @category constructors
124 * @since 2.0.0
125 */
126export const make: <Entries extends Array<readonly [string, any]>>(
127 ...entries: Entries
128) => Trie<Entries[number] extends readonly [any, infer V] ? V : never> = TR.make
129
130/**
131 * Inserts a new entry in the `Trie`.
132 *
133 * **Example** (Inserting entries)
134 *
135 * ```ts import.meta.vitest
136 * import { Trie } from "effect"
137 *
138 * const trie1 = Trie.empty<number>().pipe(
139 * Trie.insert("call", 0)
140 * )
141 * const trie2 = trie1.pipe(Trie.insert("me", 1))
142 * const trie3 = trie2.pipe(Trie.insert("mind", 2))
143 * const trie4 = trie3.pipe(Trie.insert("mid", 3))
144 *
145 * Array.from(trie1) // => [["call", 0]]
146 * Array.from(trie2) // => [["call", 0], ["me", 1]]
147 * Array.from(trie3) // => [["call", 0], ["me", 1], ["mind", 2]]
148 * Array.from(trie4) // => [["call", 0], ["me", 1], ["mid", 3], ["mind", 2]]
149 * ```
150 *
151 * @category mutations
152 * @since 2.0.0
153 */
154export const insert: {
155 <V>(key: string, value: V): (self: Trie<V>) => Trie<V>
156 <V>(self: Trie<V>, key: string, value: V): Trie<V>
157} = TR.insert
158
159/**
160 * Returns an `IterableIterator` of the keys within the `Trie`.
161 *
162 * **Details**
163 *
164 * The keys are returned in alphabetical order, regardless of insertion order.
165 *
166 * **Example** (Reading keys in alphabetical order)
167 *
168 * ```ts import.meta.vitest
169 * import { Trie } from "effect"
170 *
171 * const trie = Trie.empty<number>().pipe(
172 * Trie.insert("cab", 0),
173 * Trie.insert("abc", 1),
174 * Trie.insert("bca", 2)
175 * )
176 *
177 * Array.from(Trie.keys(trie)) // => ["abc", "bca", "cab"]
178 * ```
179 *
180 * @category getters
181 * @since 2.0.0
182 */
183export const keys: <V>(self: Trie<V>) => IterableIterator<string> = TR.keys
184
185/**
186 * Returns an `IterableIterator` of the values within the `Trie`.
187 *
188 * **Details**
189 *
190 * Values are ordered based on their key in alphabetical order, regardless of insertion order.
191 *
192 * **Example** (Reading values by key order)
193 *
194 * ```ts import.meta.vitest
195 * import { Trie } from "effect"
196 *
197 * const trie = Trie.empty<number>().pipe(
198 * Trie.insert("call", 0),
199 * Trie.insert("me", 1),
200 * Trie.insert("and", 2)
201 * )
202 *
203 * Array.from(Trie.values(trie)) // => [2, 0, 1]
204 * ```
205 *
206 * @category getters
207 * @since 2.0.0
208 */
209export const values: <V>(self: Trie<V>) => IterableIterator<V> = TR.values
210
211/**
212 * Returns an `IterableIterator` of the entries within the `Trie`.
213 *
214 * **Details**
215 *
216 * The entries are returned by keys in alphabetical order, regardless of insertion order.
217 *
218 * **Example** (Reading entries in alphabetical order)
219 *
220 * ```ts import.meta.vitest
221 * import { Trie } from "effect"
222 *
223 * const trie = Trie.empty<number>().pipe(
224 * Trie.insert("call", 0),
225 * Trie.insert("me", 1)
226 * )
227 *
228 * Array.from(Trie.entries(trie)) // => [["call", 0], ["me", 1]]
229 * ```
230 *
231 * @category getters
232 * @since 2.0.0
233 */
234export const entries: <V>(self: Trie<V>) => IterableIterator<[string, V]> = TR.entries
235
236/**
237 * Returns an `Array<[string, V]>` of the entries within the `Trie`.
238 *
239 * **Details**
240 *
241 * Equivalent to `Array.from(Trie.entries(trie))`.
242 *
243 * **Example** (Converting entries to an array)
244 *
245 * ```ts import.meta.vitest
246 * import { Trie } from "effect"
247 *
248 * const trie = Trie.empty<number>().pipe(
249 * Trie.insert("call", 0),
250 * Trie.insert("me", 1)
251 * )
252 * Trie.toEntries(trie) // => [["call", 0], ["me", 1]]
253 * ```
254 *
255 * @category getters
256 * @since 2.0.0
257 */
258export const toEntries = <V>(self: Trie<V>): Array<[string, V]> => Array.from(entries(self))
259
260/**
261 * Returns an `IterableIterator` of the keys within the `Trie`
262 * that have `prefix` as prefix (`prefix` included if it exists).
263 *
264 * **Example** (Finding keys with a prefix)
265 *
266 * ```ts import.meta.vitest
267 * import { Trie } from "effect"
268 *
269 * const trie = Trie.empty<number>().pipe(
270 * Trie.insert("she", 0),
271 * Trie.insert("shells", 1),
272 * Trie.insert("sea", 2),
273 * Trie.insert("shore", 3)
274 * )
275 *
276 * Array.from(Trie.keysWithPrefix(trie, "she")) // => ["she", "shells"]
277 * ```
278 *
279 * @category getters
280 * @since 2.0.0
281 */
282export const keysWithPrefix: {
283 (prefix: string): <V>(self: Trie<V>) => IterableIterator<string>
284 <V>(self: Trie<V>, prefix: string): IterableIterator<string>
285} = TR.keysWithPrefix
286
287/**
288 * Returns an `IterableIterator` of the values within the `Trie`
289 * that have `prefix` as prefix (`prefix` included if it exists).
290 *
291 * **Example** (Finding values with a prefix)
292 *
293 * ```ts import.meta.vitest
294 * import { Trie } from "effect"
295 *
296 * const trie = Trie.empty<number>().pipe(
297 * Trie.insert("she", 0),
298 * Trie.insert("shells", 1),
299 * Trie.insert("sea", 2),
300 * Trie.insert("shore", 3)
301 * )
302 *
303 * Array.from(Trie.valuesWithPrefix(trie, "she")) // => [0, 1]
304 * ```
305 *
306 * @category getters
307 * @since 2.0.0
308 */
309export const valuesWithPrefix: {
310 (prefix: string): <V>(self: Trie<V>) => IterableIterator<V>
311 <V>(self: Trie<V>, prefix: string): IterableIterator<V>
312} = TR.valuesWithPrefix
313
314/**
315 * Returns an `IterableIterator` of the entries within the `Trie`
316 * that have `prefix` as prefix (`prefix` included if it exists).
317 *
318 * **Example** (Finding entries with a prefix)
319 *
320 * ```ts import.meta.vitest
321 * import { Trie } from "effect"
322 *
323 * const trie = Trie.empty<number>().pipe(
324 * Trie.insert("she", 0),
325 * Trie.insert("shells", 1),
326 * Trie.insert("sea", 2),
327 * Trie.insert("shore", 3)
328 * )
329 *
330 * Array.from(Trie.entriesWithPrefix(trie, "she")) // => [["she", 0], ["shells", 1]]
331 * ```
332 *
333 * @category getters
334 * @since 2.0.0
335 */
336export const entriesWithPrefix: {
337 (prefix: string): <V>(self: Trie<V>) => IterableIterator<[string, V]>
338 <V>(self: Trie<V>, prefix: string): IterableIterator<[string, V]>
339} = TR.entriesWithPrefix
340
341/**
342 * Returns an `Array<[string, V]>` of the entries within the `Trie` whose keys
343 * start with `prefix`, including the entry for `prefix` itself when it exists.
344 *
345 * **Example** (Converting prefixed entries to an array)
346 *
347 * ```ts import.meta.vitest
348 * import { Trie } from "effect"
349 *
350 * const trie = Trie.empty<number>().pipe(
351 * Trie.insert("shells", 0),
352 * Trie.insert("sells", 1),
353 * Trie.insert("sea", 2),
354 * Trie.insert("she", 3)
355 * )
356 *
357 * Trie.toEntriesWithPrefix(trie, "she") // => [["she", 3], ["shells", 0]]
358 * ```
359 *
360 * @category getters
361 * @since 2.0.0
362 */
363export const toEntriesWithPrefix: {
364 (prefix: string): <V>(self: Trie<V>) => Array<[string, V]>
365 <V>(self: Trie<V>, prefix: string): Array<[string, V]>
366} = TR.toEntriesWithPrefix
367
368/**
369 * Returns the longest key/value in the `Trie`
370 * that is a prefix of that `key` if it exists, `None` otherwise.
371 *
372 * **Example** (Finding the longest prefix)
373 *
374 * ```ts import.meta.vitest
375 * import { Option, Trie } from "effect"
376 *
377 * const trie = Trie.empty<number>().pipe(
378 * Trie.insert("shells", 0),
379 * Trie.insert("sells", 1),
380 * Trie.insert("she", 2)
381 * )
382 *
383 * Trie.longestPrefixOf(trie, "sell") // => Option.none()
384 * Trie.longestPrefixOf(trie, "sells") // => Option.some(["sells", 1])
385 * ```
386 *
387 * @category getters
388 * @since 2.0.0
389 */
390export const longestPrefixOf: {
391 (key: string): <V>(self: Trie<V>) => Option<[string, V]>
392 <V>(self: Trie<V>, key: string): Option<[string, V]>
393} = TR.longestPrefixOf
394
395/**
396 * Returns the size of the `Trie` (number of entries in the `Trie`).
397 *
398 * **Example** (Getting the size)
399 *
400 * ```ts import.meta.vitest
401 * import { Trie } from "effect"
402 *
403 * const trie = Trie.empty<number>().pipe(
404 * Trie.insert("a", 0),
405 * Trie.insert("b", 1)
406 * )
407 *
408 * Trie.size(trie) // => 2
409 * ```
410 *
411 * @category getters
412 * @since 2.0.0
413 */
414export const size: <V>(self: Trie<V>) => number = TR.size
415
416/**
417 * Looks up the value for the specified key in the `Trie` safely.
418 *
419 * **Example** (Looking up values safely)
420 *
421 * ```ts import.meta.vitest
422 * import { Option, Trie } from "effect"
423 *
424 * const trie = Trie.empty<number>().pipe(
425 * Trie.insert("call", 0),
426 * Trie.insert("me", 1),
427 * Trie.insert("mind", 2),
428 * Trie.insert("mid", 3)
429 * )
430 *
431 * Trie.get(trie, "call") // => Option.some(0)
432 * Trie.get(trie, "me") // => Option.some(1)
433 * Trie.get(trie, "mind") // => Option.some(2)
434 * Trie.get(trie, "mid") // => Option.some(3)
435 * Trie.get(trie, "cale") // => Option.none()
436 * Trie.get(trie, "ma") // => Option.none()
437 * Trie.get(trie, "midn") // => Option.none()
438 * Trie.get(trie, "mea") // => Option.none()
439 * ```
440 *
441 * @category getters
442 * @since 2.0.0
443 */
444export const get: {
445 (key: string): <V>(self: Trie<V>) => Option<V>
446 <V>(self: Trie<V>, key: string): Option<V>
447} = TR.get
448
449/**
450 * Checks whether the given key exists in the `Trie`.
451 *
452 * **Example** (Checking key membership)
453 *
454 * ```ts import.meta.vitest
455 * import { Trie } from "effect"
456 *
457 * const trie = Trie.empty<number>().pipe(
458 * Trie.insert("call", 0),
459 * Trie.insert("me", 1),
460 * Trie.insert("mind", 2),
461 * Trie.insert("mid", 3)
462 * )
463 *
464 * Trie.has(trie, "call") // => true
465 * Trie.has(trie, "me") // => true
466 * Trie.has(trie, "mind") // => true
467 * Trie.has(trie, "mid") // => true
468 * Trie.has(trie, "cale") // => false
469 * Trie.has(trie, "ma") // => false
470 * Trie.has(trie, "midn") // => false
471 * Trie.has(trie, "mea") // => false
472 * ```
473 *
474 * @category predicates
475 * @since 2.0.0
476 */
477export const has: {
478 (key: string): <V>(self: Trie<V>) => boolean
479 <V>(self: Trie<V>, key: string): boolean
480} = TR.has
481
482/**
483 * Returns `true` when the `Trie` contains no entries.
484 *
485 * **Example** (Checking whether a trie is empty)
486 *
487 * ```ts import.meta.vitest
488 * import { Trie } from "effect"
489 *
490 * const trie = Trie.empty<number>()
491 * const trie1 = trie.pipe(Trie.insert("ma", 0))
492 *
493 * Trie.isEmpty(trie) // => true
494 * Trie.isEmpty(trie1) // => false
495 * ```
496 *
497 * @category predicates
498 * @since 2.0.0
499 */
500export const isEmpty: <V>(self: Trie<V>) => boolean = TR.isEmpty
501
502/**
503 * Looks up the value for the specified key in the `Trie` unsafely.
504 *
505 * **When to use**
506 *
507 * Use when the trie key is known to exist and a missing key should be treated
508 * as a programming error.
509 *
510 * **Gotchas**
511 *
512 * `getUnsafe` throws if the key is not found. Use `get` instead to safely get
513 * a value from the `Trie`.
514 *
515 * **Example** (Looking up values unsafely)
516 *
517 * ```ts import.meta.vitest
518 * import { Result, Trie } from "effect"
519 *
520 * const trie = Trie.empty<number>().pipe(
521 * Trie.insert("call", 0),
522 * Trie.insert("me", 1)
523 * )
524 *
525 * Result.try({
526 * try: () => Trie.getUnsafe(trie, "mae"),
527 * catch: (error) => (error as Error).message
528 * }) // => Result.fail("Expected trie to contain key")
529 * ```
530 *
531 * @category unsafe
532 * @since 4.0.0
533 */
534export const getUnsafe: {
535 (key: string): <V>(self: Trie<V>) => V
536 <V>(self: Trie<V>, key: string): V
537} = TR.getUnsafe
538
539/**
540 * Removes the entry for the specified key in the `Trie`.
541 *
542 * **Example** (Removing entries)
543 *
544 * ```ts import.meta.vitest
545 * import { Option, Trie } from "effect"
546 *
547 * const trie = Trie.empty<number>().pipe(
548 * Trie.insert("call", 0),
549 * Trie.insert("me", 1),
550 * Trie.insert("mind", 2),
551 * Trie.insert("mid", 3)
552 * )
553 *
554 * const trie1 = trie.pipe(Trie.remove("call"))
555 * const trie2 = trie1.pipe(Trie.remove("mea"))
556 *
557 * Trie.get(trie, "call") // => Option.some(0)
558 * Trie.get(trie1, "call") // => Option.none()
559 * Trie.get(trie2, "call") // => Option.none()
560 * ```
561 *
562 * @category mutations
563 * @since 2.0.0
564 */
565export const remove: {
566 (key: string): <V>(self: Trie<V>) => Trie<V>
567 <V>(self: Trie<V>, key: string): Trie<V>
568} = TR.remove
569
570/**
571 * Reduces a state over the entries of the `Trie`.
572 *
573 * **Example** (Reducing entries)
574 *
575 * ```ts import.meta.vitest
576 * import { Trie } from "effect"
577 *
578 * const trie = Trie.empty<number>().pipe(
579 * Trie.insert("shells", 0),
580 * Trie.insert("sells", 1),
581 * Trie.insert("she", 2)
582 * )
583 *
584 * trie.pipe(Trie.reduce(0, (acc, n) => acc + n)) // => 3
585 * trie.pipe(Trie.reduce(10, (acc, n) => acc + n)) // => 13
586 * trie.pipe(Trie.reduce("", (acc, _, key) => acc + key)) // => "sellssheshells"
587 * ```
588 *
589 * @category folding
590 * @since 2.0.0
591 */
592export const reduce: {
593 <Z, V>(zero: Z, f: (accumulator: Z, value: V, key: string) => Z): (self: Trie<V>) => Z
594 <Z, V>(self: Trie<V>, zero: Z, f: (accumulator: Z, value: V, key: string) => Z): Z
595} = TR.reduce
596
597/**
598 * Maps over the entries of the `Trie` using the specified function.
599 *
600 * **Example** (Mapping entries)
601 *
602 * ```ts import.meta.vitest
603 * import { Trie } from "effect"
604 *
605 * const trie = Trie.empty<number>().pipe(
606 * Trie.insert("shells", 0),
607 * Trie.insert("sells", 1),
608 * Trie.insert("she", 2)
609 * )
610 *
611 * Trie.map(trie, (v) => v + 1) // => Trie.make(["shells", 1], ["sells", 2], ["she", 3])
612 * Trie.map(trie, (_, k) => k.length) // => Trie.make(["shells", 6], ["sells", 5], ["she", 3])
613 * ```
614 *
615 * @category folding
616 * @since 2.0.0
617 */
618export const map: {
619 <A, V>(f: (value: V, key: string) => A): (self: Trie<V>) => Trie<A>
620 <V, A>(self: Trie<V>, f: (value: V, key: string) => A): Trie<A>
621} = TR.map
622
623/**
624 * Filters entries out of a `Trie` using the specified predicate.
625 *
626 * **Example** (Filtering entries)
627 *
628 * ```ts import.meta.vitest
629 * import { Trie } from "effect"
630 *
631 * const trie = Trie.empty<number>().pipe(
632 * Trie.insert("shells", 0),
633 * Trie.insert("sells", 1),
634 * Trie.insert("she", 2)
635 * )
636 *
637 * Trie.filter(trie, (v) => v > 1) // => Trie.make(["she", 2])
638 * Trie.filter(trie, (_, k) => k.length > 3) // => Trie.make(["shells", 0], ["sells", 1])
639 * ```
640 *
641 * @category filtering
642 * @since 2.0.0
643 */
644export const filter: {
645 <A, B extends A>(f: (a: NoInfer<A>, k: string) => a is B): (self: Trie<A>) => Trie<B>
646 <A>(f: (a: NoInfer<A>, k: string) => boolean): (self: Trie<A>) => Trie<A>
647 <A, B extends A>(self: Trie<A>, f: (a: A, k: string) => a is B): Trie<B>
648 <A>(self: Trie<A>, f: (a: A, k: string) => boolean): Trie<A>
649} = TR.filter
650
651/**
652 * Maps over the entries of the `Trie` using the specified filter and keeps
653 * only successful results.
654 *
655 * **Example** (Filtering and mapping entries)
656 *
657 * ```ts import.meta.vitest
658 * import { Result, Trie } from "effect"
659 *
660 * const trie = Trie.empty<number>().pipe(
661 * Trie.insert("shells", 0),
662 * Trie.insert("sells", 1),
663 * Trie.insert("she", 2)
664 * )
665 *
666 * Trie.filterMap(trie, (v) => v > 1 ? Result.succeed(v) : Result.failVoid) // => Trie.make(["she", 2])
667 * Trie.filterMap(
668 * trie,
669 * (v, k) => k.length > 3 ? Result.succeed(v) : Result.failVoid
670 * ) // => Trie.make(["shells", 0], ["sells", 1])
671 * ```
672 *
673 * @category filtering
674 * @since 2.0.0
675 */
676export const filterMap: {
677 <A, B, X>(f: (input: A, key: string) => Result<B, X>): (self: Trie<A>) => Trie<B>
678 <A, B, X>(self: Trie<A>, f: (input: A, key: string) => Result<B, X>): Trie<B>
679} = TR.filterMap
680
681/**
682 * Filters out `None` values from a `Trie` of `Options`s.
683 *
684 * **Example** (Compacting optional values)
685 *
686 * ```ts import.meta.vitest
687 * import { Option, Trie } from "effect"
688 *
689 * const trie = Trie.empty<Option.Option<number>>().pipe(
690 * Trie.insert("shells", Option.some(0)),
691 * Trie.insert("sells", Option.none()),
692 * Trie.insert("she", Option.some(2))
693 * )
694 *
695 * Trie.compact(trie) // => Trie.make(["shells", 0], ["she", 2])
696 * ```
697 *
698 * @category filtering
699 * @since 2.0.0
700 */
701export const compact: <A>(self: Trie<Option<A>>) => Trie<A> = TR.compact
702
703/**
704 * Applies the specified function to the entries of the `Trie`.
705 *
706 * **Example** (Iterating over entries)
707 *
708 * ```ts import.meta.vitest
709 * import { Trie } from "effect"
710 *
711 * let value = 0
712 *
713 * Trie.empty<number>().pipe(
714 * Trie.insert("shells", 0),
715 * Trie.insert("sells", 1),
716 * Trie.insert("she", 2),
717 * Trie.forEach((n, key) => {
718 * value += n + key.length
719 * })
720 * )
721 *
722 * value // => 17
723 * ```
724 *
725 * @category traversing
726 * @since 2.0.0
727 */
728export const forEach: {
729 <V>(f: (value: V, key: string) => void): (self: Trie<V>) => void
730 <V>(self: Trie<V>, f: (value: V, key: string) => void): void
731} = TR.forEach
732
733/**
734 * Updates the value of the specified key within the `Trie` if it exists.
735 *
736 * **Example** (Modifying an existing value)
737 *
738 * ```ts import.meta.vitest
739 * import { Option, Trie } from "effect"
740 *
741 * const trie = Trie.empty<number>().pipe(
742 * Trie.insert("shells", 0),
743 * Trie.insert("sells", 1),
744 * Trie.insert("she", 2)
745 * )
746 *
747 * trie.pipe(Trie.modify("she", (v) => v + 10), Trie.get("she")) // => Option.some(12)
748 * trie.pipe(Trie.modify("me", (v) => v)) // => trie
749 * ```
750 *
751 * @category mutations
752 * @since 2.0.0
753 */
754export const modify: {
755 <V>(key: string, f: (v: V) => V): (self: Trie<V>) => Trie<V>
756 <V>(self: Trie<V>, key: string, f: (v: V) => V): Trie<V>
757} = TR.modify
758
759/**
760 * Removes all entries in the `Trie` which have the specified keys.
761 *
762 * **Example** (Removing multiple entries)
763 *
764 * ```ts import.meta.vitest
765 * import { Trie } from "effect"
766 *
767 * const trie = Trie.empty<number>().pipe(
768 * Trie.insert("shells", 0),
769 * Trie.insert("sells", 1),
770 * Trie.insert("she", 2)
771 * )
772 *
773 * trie.pipe(Trie.removeMany(["she", "sells"])) // => Trie.make(["shells", 0])
774 * ```
775 *
776 * @category mutations
777 * @since 2.0.0
778 */
779export const removeMany: {
780 (keys: Iterable<string>): <V>(self: Trie<V>) => Trie<V>
781 <V>(self: Trie<V>, keys: Iterable<string>): Trie<V>
782} = TR.removeMany
783
784/**
785 * Inserts multiple entries in the `Trie` at once.
786 *
787 * **Example** (Inserting multiple entries)
788 *
789 * ```ts import.meta.vitest
790 * import { Trie } from "effect"
791 *
792 * const trie = Trie.empty<number>().pipe(
793 * Trie.insert("shells", 0)
794 * )
795 *
796 * trie.pipe(
797 * Trie.insertMany([["sells", 1], ["she", 2]])
798 * ) // => Trie.make(["shells", 0], ["sells", 1], ["she", 2])
799 * ```
800 *
801 * @category mutations
802 * @since 2.0.0
803 */
804export const insertMany: {
805 <V>(iter: Iterable<[string, V]>): (self: Trie<V>) => Trie<V>
806 <V>(self: Trie<V>, iter: Iterable<[string, V]>): Trie<V>
807} = TR.insertMany