10 Generic Algorithms and Iterators
This chapter introduces generic algorithms as reusable building blocks that work across many data structures by operating on iterables rather than concrete containers. It generalizes familiar higher‑order functions—map, filter, and reduce—from arrays to any Iterable
The text then deepens the iterator model beyond the JavaScript standard by defining capability‑oriented categories that unlock more efficient implementations. Input and output iterators support one‑pass reading or writing; forward iterators add cloning and in‑place mutation, enabling functions like find that return an iterator positioned at the match so callers can modify data. Bidirectional iterators add decrement to traverse in both directions, which enables a generalized, in‑place reverse that works across any structure supporting backward movement. Random‑access iterators add constant‑time jumps and distance measurement, powering O(1) indexing (elementAt) and efficient algorithms (e.g., binary search and comparison‑based sorts) that need to “jump” within a range. Throughout, the chapter connects iterator capability to time and space complexity, showing how stronger categories enable faster, in‑place algorithms.
Finally, the chapter presents adaptive algorithms that choose the most efficient implementation available from what the iterator supports, without sacrificing generality. Using elementAt as an example, it provides both a linear‑time version for forward iterators and a constant‑time version for random‑access iterators, with a small type guard to dispatch between them. The overarching guidance is to require the weakest iterator that suffices to maximize applicability, while providing specialized, faster paths when more capable iterators are present. The key takeaways are to favor library algorithms over loops, leverage fluent pipelines for clarity, use type constraints to express contracts, and recognize that richer iterator capabilities systematically unlock more efficient, reusable, and data‑structure‑agnostic algorithms; the chapter also hints at ranges as a future‑friendly abstraction for composing such operations fluently.
Reversing a sequence using a stack: elements from the original sequence get pushed on the stack, then popped to produce the reversed sequence.
Reversing an array in-place by swapping its elements.
Begin and end iterators define a range: begin points to the first element while end points past the last element.
An input iterator can retrieve the value of the current element and advance to the next element.
A forward iterator can read and write the value of the current element, advance to the next element, and also create a clone of itself, which enables multiple traversals. In this figure we see how clone() creates a copy of the iterator. As we advance the original, the clone doesn’t move.
A bidirectional iterator can read and write the value of the current element, clone itself, and step both forwards and backwards.
A random-access iterator can read and write the value of the current element, clone itself, and move backwards or forwards any number of steps.
FAQ
What are generic algorithms and why do they use iterators?
Generic algorithms are reusable functions that operate over sequences without caring about the underlying data structure. By targeting iterables/iterators (instead of arrays only), the same algorithm works for arrays, trees, lists, streams, and more, improving reuse and composability.How are map(), filter(), and reduce() generalized beyond arrays in TypeScript?
Use Iterable<T> instead of T[]. map and filter can be implemented as generator functions that yield transformed/filtered values, while reduce consumes an Iterable<T> and returns a single value. This makes them applicable to any iterable data structure.Why should I prefer library algorithms and pipelines over manual loops?
- Fewer bugs: algorithms are well-tested and declarative- Readability: intent is clear (e.g., filter → map → reduce)
- Reuse and composability: the same building blocks solve many problems
Write loops only when an algorithm/pipeline cannot express the task.
What is a fluent pipeline and how does FluentIterable help?
A fluent pipeline chains operations left-to-right via method calls (e.g., .filter(...).map(...).reduce(...)). Wrapping an iterable in a FluentIterable<T> lets methods like map and filter return another FluentIterable, enabling natural chaining while reduce returns a final value.What are type parameter constraints and when should I use them?
Constraints (T extends SomeInterface) restrict which types can instantiate a generic so required members exist. Examples: T extends IRenderable for renderAll to call render(); T extends IComparable<T> for max/clamp; or IHashable for keys in hash-based structures.Which iterator categories exist and what do they enable?
- Input: read and advance once (streams, generators)- Output: write and advance (sinks like console/IO)
- Forward: read/write, advance, clone (multi-pass, in-place updates)
- Bidirectional: forward + backward steps (e.g., doubly linked lists, arrays)
- Random-access: jump arbitrarily and measure distance (arrays); needed for most O(n log n) sorts and binary search.
How do you implement an efficient in-place reverse() generically?
Require bidirectional iterators. Maintain begin/end, swap values, then begin.increment() and end.decrement() until they meet. This runs in O(n) time and O(1) extra space and works for any structure that supports bidirectional iteration (e.g., arrays, doubly linked lists).When should I use a forward vs bidirectional vs random-access iterator?
- Forward: single-direction multi-pass and in-place updates (e.g., find that returns an iterator you can set)- Bidirectional: algorithms needing both directions (e.g., reverse in-place)
- Random-access: algorithms needing jumps (e.g., binary search, quickselect, efficient elementAt in O(1)).
What are adaptive algorithms and how do they choose an implementation?
Adaptive algorithms provide multiple implementations and pick the most efficient one based on iterator capabilities at runtime. Example: elementAt uses O(1) move/distance for random-access iterators, otherwise falls back to O(n) forward iteration.Which other common pipeline algorithms should I know (and synonyms)?
- any/all/none: predicate checks over a sequence- take (limit), drop (skip): window the sequence
- zip: pair elements from two sequences
- reduce (fold/collect/accumulate/aggregate): combine to one value
- map (fmap/select) and filter (where): transform/select elements
Programming with Types ebook for free
