12. Collections, Generics and Functional Programming Idioms

Introduction and Context

Most useful programs manipulate groups of values rather than isolated objects. A web application may maintain users, orders, permissions, products, messages, or search results. The quality of such software depends not only on the values stored but also on how they are organized, accessed, transformed, and protected from accidental change.

Collections provide reusable structures for representing groups of objects. Generics allow these structures and algorithms to remain type-safe while operating on many data types. Functional programming idioms add a complementary way of expressing computation: instead of describing every control-flow step, a programmer can describe transformations, selections, aggregations, and combinations of values. Together, these features support concise, reusable, maintainable, and reliable software.

This chapter uses Java-like notation because it clearly demonstrates interfaces such as `List`, `Set`, `Map`, `Iterator`, `Comparator`, `Stream`, and `Optional`. The underlying principles apply equally to C#, Kotlin, TypeScript, Python, and other modern languages.

Learning Objectives

After studying this chapter, a learner should be able to:

• distinguish among major collection abstractions and select one according to semantics and performance;
• explain generic types, bounded type parameters, wildcards, variance, and type safety;
• use iterators, comparators, and ordering strategies correctly;
• construct lambda expressions and higher-order operations;
• design functional pipelines involving filtering, mapping, sorting, grouping, and reduction;
• recognize the benefits and risks of immutable data;
• analyze collection-based solutions in terms of complexity, readability, memory, and concurrency;
• apply these ideas to a realistic software-development problem.

Collections as Models of Meaning

A collection is not merely a container. Its interface communicates what relationships matter. A `List` represents an ordered sequence and may contain duplicates. A `Set` represents membership, normally without duplicates. A `Map` represents associations between keys and values. Choosing an inappropriate abstraction often creates defects even when the program compiles.

Lists, sets, queues, and maps

An array provides indexed storage with a fixed size. A dynamic array such as Java’s `ArrayList` preserves insertion order and offers efficient random access. Appending is normally amortized constant time, while inserting near the beginning may require shifting many elements. A linked list can insert or remove efficiently when a node position is already known, but indexed access is linear and memory locality is usually poorer. Consequently, linked lists are not a universal improvement over array-based lists.

A `Set` is suitable when uniqueness is part of the domain. `HashSet` generally provides expected constant-time insertion, removal, and membership testing, but does not promise sorted iteration. `LinkedHashSet` preserves insertion order, while `TreeSet` maintains sorted order and typically provides logarithmic operations. The choice therefore depends on whether the program needs fast membership, predictable insertion order, or ordered traversal.

A `Map` stores key–value associations. `HashMap` is appropriate for general lookup by key. `LinkedHashMap` preserves a defined traversal order and is useful for predictable output or simple cache policies. `TreeMap` maintains keys in sorted order and supports range-oriented operations. A map should not be used merely because it is convenient: the key must represent a meaningful identity, and its equality and hash behavior must be correct.

Queues and deques model processing order. A FIFO queue is appropriate for work scheduling, while a deque supports insertion and removal at both ends. A priority queue removes the element with the highest priority according to a comparator, not necessarily the earliest inserted element. These distinctions are semantic, not cosmetic.

Complexity and representation

Collection selection should consider at least four dimensions: semantic fit, time complexity, space consumption, and operational behavior under realistic workloads. Big-O notation describes growth, but constants, memory locality, resizing, allocation, and access patterns also matter. For example, a hash table may provide expected constant-time lookup but can degrade under poor hashing or adversarial input. A sorted tree offers logarithmic operations and ordered traversal, sometimes eliminating the need for a separate sorting phase.

A useful engineering question is: “What operation dominates this component?” If the answer is membership testing, a set may be preferable to a list. If the answer is sequential rendering, a list may be clearer. If records are repeatedly retrieved by identifier, a map is usually more expressive and efficient.

Generics: Reuse Without Surrendering Type Safety

Generics parameterize a class, interface, or method by a type. `List<String>` states that the list is intended to contain strings. This prevents many invalid operations at compile time and removes repeated casts.

```java

List<String> names = new ArrayList<>();

names.add("Asha");

String first = names.get(0);

```

The compiler can verify the relationship between the collection and its elements. This is safer than a raw collection containing values of unrelated types.

A generic method introduces its own type variable:

```java

static <T> T first(List<T> values) {

if (values.isEmpty()) throw new IllegalArgumentException();

return values.get(0);

}

```

The method works for any element type while preserving that type in the result. Generic classes similarly express reusable abstractions such as `Repository<T>`, `Pair<A, B>`, or `Result<T>`.

Bounds and variance

An upper bound restricts a type parameter to a family of types:

```java

static <T extends Number> double total(List<T> values) {

double result = 0;

for (T value : values) result += value.doubleValue();

return result;

}

```

A wildcard describes an unknown type. `List<?>` means a list of some type that the method does not need to know. It is safe to read values as `Object`, but it is generally unsafe to add arbitrary values.

The producer–consumer rule is a practical guide: use `? extends T` when a structure produces values of type `T`, and `? super T` when it consumes values of type `T`.

```java

static double sum(List<? extends Number> values) { ... }

static void addDefaults(List<? super Integer> values) { ... }

```

The first method can read numbers from a list of integers, doubles, or other numeric subtypes. The second can safely add integers to a list of integers, numbers, or objects. This issue is commonly called variance. Generic types are often invariant: a `List<Integer>` is not a subtype of `List<Number>`, because otherwise code could insert a `Double` into it.

Type erasure in Java means that generic type information is primarily enforced at compile time and is not fully available at runtime. This explains restrictions such as the inability to create `new T()` directly and the difficulty of creating arrays of a type variable. These limitations encourage the use of factories, class tokens, or collection constructors supplied by the caller.

Traversal, Iteration, and Ordering

The enhanced `for` loop is a readable way to traverse an iterable collection. An `Iterator` is useful when traversal must support controlled removal or when an API should expose sequential access without revealing representation.

```java

Iterator<Order> iterator = orders.iterator();

while (iterator.hasNext()) {

Order order = iterator.next();

if (order.isCancelled()) iterator.remove();

}

```

Removing directly from a collection during a for-each traversal can cause a concurrent-modification failure. The iterator’s removal operation, where supported, expresses the intended mutation safely for that traversal model. In concurrent systems, fail-fast behavior should not be mistaken for synchronization; it is primarily a debugging aid.

Ordering has two distinct meanings. A type’s natural ordering is represented by `Comparable<T>`. A context-specific ordering is represented by `Comparator<T>`.

```java

Comparator<Order> byAmountThenDate =

Comparator.comparing(Order::amount)

.thenComparing(Order::date);

```

A comparator should be transitive, consistent, and compatible with equality when used by sorted sets or maps. If two objects compare as equal, a `TreeSet` may treat them as duplicates even when `equals` says otherwise. This is a subtle but important source of data loss.

Null handling, descending order, locale-sensitive strings, and numeric overflow also require deliberate decisions. For example, subtracting two integers to compare them can overflow; a library comparison method is safer.

Functional Programming Idioms

Functional programming treats computation as the evaluation and composition of functions. In an object-oriented language, this does not require abandoning objects. Rather, functions become values that can be passed to methods, returned from methods, and stored in variables.

A lambda expression is an anonymous function:

```java

Predicate<User> active = user -> user.isActive();

Function<User, String> email = User::email;

Consumer<User> audit = user -> log(user.id());

```

A `Predicate<T>` returns a boolean, a `Function<T,R>` transforms a value, a `Consumer<T>` performs an action without returning a value, and a `Supplier<T>` produces a value without input. Method references are a compact form of suitable lambdas.

Higher-order operations accept or return functions. They allow a method to express policy separately from mechanism. A generic sorting method can accept a comparator; a filtering method can accept a predicate; a retry mechanism can accept a supplier. This separation improves reuse and testing.

Streams and pipelines

A stream is a description of a sequence of computations over data. A typical pipeline has three stages:

1. a source, such as a collection;

2. intermediate operations, such as `filter`, `map`, `sorted`, or `distinct`;

3. a terminal operation, such as `toList`, `reduce`, `count`, `findFirst`, or `forEach`.

```java

List<String> premiumEmails = customers.stream()

.filter(Customer::isPremium)

.map(Customer::email)

.map(String::toLowerCase)

.distinct()

.sorted()

.toList();

```

Intermediate operations are generally lazy: they describe work that is performed when a terminal operation requests results. This enables short-circuiting operations such as `findFirst`, `anyMatch`, and `limit`. A pipeline should be read as a data transformation, not as a reusable collection; a stream is normally consumed once.

`map` changes each element’s representation. `filter` retains selected elements. `flatMap` replaces each element with a stream and flattens the results, making it suitable for nested collections. `reduce` combines values using an associative operation, while collectors support structured results such as lists, maps, groups, and summaries.

```java

Map<Department, Long> counts = employees.stream()

.collect(Collectors.groupingBy(Employee::department,

Collectors.counting()));

```

A pipeline is not automatically superior to a loop. It is valuable when the transformation is naturally compositional and side-effect free. A loop may be clearer for complex stateful logic, detailed error handling, or performance-critical code requiring careful allocation control.

Purity, side effects, and parallelism

A pure function gives the same output for the same input and does not modify observable external state. Pure transformations are easier to test, cache, parallelize, and reason about. By contrast, this pattern is risky:

```java

List<String> result = new ArrayList<>();

users.stream().filter(User::isActive).forEach(u -> result.add(u.email()));

```

It introduces an external mutable accumulator. A collector or `map(...).toList()` communicates the operation more clearly. Side effects are sometimes necessary—for example, writing to a database—but should occur at an explicit boundary rather than being scattered through intermediate operations.

Parallel streams can help with large, independent, CPU-bound workloads, but they add scheduling overhead and require associative operations, thread-safe behavior, and suitable data partitioning. They are usually inappropriate for blocking input/output, small collections, order-sensitive effects, or code that relies on shared mutable state. Performance should be measured rather than assumed.

Immutable Data and Defensive Design

An immutable object cannot change after construction. Immutable collections prevent callers from altering a data structure through an exposed reference. Immutability reduces aliasing: if several components share a value, one component cannot silently change what others observe.

```java

record UserProfile(String id, String displayName, List<String> roles) {

UserProfile {

roles = List.copyOf(roles);

}

}

```

The defensive copy prevents later changes to the caller’s list from changing the profile. However, immutability is transitive only when contained objects are also immutable. An unmodifiable view may prevent mutation through one reference while the underlying collection remains mutable elsewhere; a true copy has different semantics.

Immutable values support safer concurrency, clearer APIs, reliable caching, and easier testing. They may require additional allocation, although structural sharing and persistent data structures can reduce copying in specialized libraries. The appropriate design is not “immutable at any cost,” but deliberate control over ownership and mutation.

A Decision Framework for Collection-Based Design

A practical selection process begins with the domain question. Does the data represent sequence, uniqueness, association, priority, or insertion history? Next identify dominant operations: indexed access, membership, key lookup, ordered traversal, insertion at an end, or removal at an arbitrary position. Then consider constraints such as null policy, thread safety, memory, stable iteration, and mutation ownership.

The following principles are useful:

• Prefer the narrowest interface required by clients, such as `List` or `Map`, rather than exposing a concrete implementation.
• Choose a hash-based structure for membership or lookup when ordering is irrelevant.
• Choose a sorted structure when ordered access or range queries are central.
• Use immutable or unmodifiable results at boundaries where ownership must be protected.
• Supply comparators explicitly when different views of order are meaningful.
• Use generics to express contracts and avoid raw types.
• Measure before replacing a clear solution with a more complex optimization.

Applied Case: Designing a Product-Search Service

Background

Consider an illustrative case involving ShopSphere, a retail platform whose product-search service receives a catalogue of products and returns recommendations for a customer. Each product has an identifier, category, price, stock status, rating, and set of tags.

Situation and problem

The initial implementation stores products in a list and repeatedly scans the entire catalogue to locate an identifier, remove duplicate products, and display results ordered by rating. Under a growing catalogue, response time becomes unpredictable. The code also returns its internal mutable list, allowing callers to alter service state.

Analysis

The service has several distinct requirements. Identifier lookup is a map operation. Duplicate tags are a set concern. Search results are ordered sequences. A catalogue keyed by product identifier is therefore more expressive than a single list. The service should also distinguish its internal storage from externally returned results.

Approach and solution

The service maintains `Map<ProductId, Product>` for direct lookup. Product tags are represented by an immutable set. Search accepts a predicate and a comparator, allowing different clients to request different policies without duplicating traversal logic.

```java

List<Product> search(Predicate<Product> condition,

Comparator<Product> order) {

return catalogue.values().stream()

.filter(condition)

.sorted(order)

.toList();

}

```

A request for in-stock electronics can use a predicate combining category and stock status. A comparator can order by rating descending and price ascending. The returned list is a new unmodifiable result, so clients cannot corrupt the catalogue. Generic repository methods ensure that identifiers and products are associated consistently.

Outcome

The design makes each requirement visible in the type and collection choices. Lookup no longer requires a full scan, ordering is supplied at the point of use, and the service controls mutation. The approach also improves testing: predicates, comparators, and repository behavior can be tested independently.

Learning points

The case demonstrates that performance improvement begins with semantic modeling. Functional pipelines are useful because the operation is a sequence of filtering, ordering, and materialization. They are not a substitute for selecting an appropriate primary data structure. It also shows why immutability at API boundaries is a reliability and governance decision, not merely a stylistic preference.

Challenges, Risks, and Professional Considerations

Common mistakes include using a list for repeated membership tests, relying on hash iteration order, exposing mutable internals, using raw types, writing comparators inconsistent with equality, and modifying a collection during traversal. Another error is assuming that a stream pipeline automatically improves performance. Readability, allocation, branching, and workload size must be evaluated.

Functional code can conceal expensive operations. Calling `sorted`, `distinct`, or `collect` may require additional memory. Repeatedly converting between collections can create unnecessary allocation. A `flatMap` over a very large nested structure may be elegant but costly. Profiling should identify actual bottlenecks.

Collection APIs also have security implications. Untrusted input can create excessive memory consumption, pathological hash behavior, or denial-of-service conditions. Limits on collection sizes, validation of keys, and careful handling of user-controlled sorting criteria are important in public services.

From an ethical and governance perspective, data structures do not remove obligations concerning privacy and fairness. A collection of customer records must have appropriate access control, retention rules, and minimization. Ordering and filtering algorithms may affect which products, applicants, or messages are shown first. Where these decisions influence people, the organization should document criteria, monitor outcomes, and provide responsible oversight.

Contemporary Developments

Modern languages increasingly combine object-oriented and functional features. Records, pattern matching, persistent collections, null-safety mechanisms, and sequence-processing libraries reduce accidental mutation and boilerplate. Reactive streams extend pipeline ideas to asynchronous, potentially unbounded data, adding concerns such as back-pressure and cancellation.

Data-oriented systems and columnar processing libraries optimize collections for analytics rather than general object manipulation. In distributed systems, collection operations may be translated into database queries or executed across nodes; apparently simple transformations then involve serialization, network cost, partitioning, and fault tolerance. Developers should therefore understand whether a pipeline runs in memory, in a database, or across a distributed engine.

Best Practices

Use collection interfaces in public contracts and concrete implementations internally. Document ordering, duplicate, null, and mutation policies. Prefer meaningful generic constraints. Keep transformations pure where possible and isolate side effects. Use `Comparator` factories rather than fragile subtraction-based comparisons. Return defensive or immutable results when callers should not own internal state. Select parallel execution only after measuring a suitable workload. Finally, review collection choices as part of domain modeling, complexity analysis, testing, and security review.

Chapter Summary

Collections express different data relationships: lists model ordered sequences, sets model uniqueness, maps model key–value associations, and queues model processing order. Their selection should reflect semantics, dominant operations, complexity, memory, ordering, and ownership requirements. Generics provide reusable abstractions with compile-time type safety; bounds and wildcards express controlled flexibility and variance.

Iterators support structured traversal, while comparators define context-specific ordering. Lambda expressions and higher-order functions make behavior composable. Stream pipelines provide declarative filtering, mapping, flattening, sorting, grouping, and reduction, but they should not be used mechanically or with uncontrolled side effects. Immutable data reduces aliasing and supports safer APIs and concurrency. Professional design combines these techniques with measurement, security, privacy, and responsible governance.

Key Terms

Collection: An abstraction representing a group of values or objects.

List: An ordered collection that may contain duplicate elements.

Set: A collection whose defining property is uniqueness of elements.

Map: A structure associating keys with values.

Queue: A collection designed for ordered processing of elements.

Generic type: A type parameterized by one or more type variables.

Type parameter: A symbolic type variable used in a generic declaration.

Bound: A restriction specifying acceptable types for a type parameter.

Wildcard: A notation representing an unknown generic type.

Variance: The relationship between generic types and subtype relationships.

Iterator: An object that provides controlled sequential traversal.

Comparator: A strategy for comparing two objects and defining an ordering.

Lambda expression: An anonymous function that can be passed as a value.

Higher-order function: A function that accepts or returns another function.

Stream: A potentially lazy description of operations over a sequence of values.

Pipeline: A composed sequence of stream transformations and a terminal operation.

Pure function: A function without observable side effects whose result depends only on its inputs.

Immutability: The property of an object or structure that prevents state changes after construction.

Reduction: The combination of multiple values into one accumulated result.

Structural sharing: Reuse of unchanged parts between versions of an immutable structure.

Review Questions

Short Answer Questions

1. What semantic distinction separates a `List` from a `Set`?

2. Why is `List<Integer>` not generally a subtype of `List<Number>`?

3. What is the purpose of an `Iterator`?

4. Distinguish between `map` and `filter` in a functional pipeline.

5. Why can an unmodifiable view differ from an immutable copy?

Long Answer Questions

1. Explain how semantic requirements and complexity considerations influence the choice among lists, sets, maps, and sorted collections.

2. Discuss generic methods, bounded type parameters, wildcards, and the producer–consumer rule.

3. Explain the structure and execution behavior of a stream pipeline, including laziness and terminal operations.

4. Analyze the relationship between comparators, natural ordering, equality, and sorted collections.

5. Discuss the benefits, costs, and professional risks of immutable data and side-effect-free programming.

Analytical / Application Questions

1. A service repeatedly checks whether thousands of identifiers exist and does not need insertion order. Which collection would you choose, and what trade-offs should be reviewed?

2. Design a generic method that accepts numeric values for reading and another method that safely inserts integers into a suitably general collection. Explain the bounds used.

3. A parallel stream updates a shared mutable list while processing customer records. Analyze the risks and propose a clearer alternative.

22. Multiple Choice Questions with Answers

Question 1

A service needs fast membership testing, does not require ordering, and must prevent duplicates. Which collection is the most appropriate starting choice?

A. ArrayList

B. HashSet

C. LinkedList

D. PriorityQueue

Correct Answer: B. HashSet

Question 2

What does `List<? extends Number>` primarily allow a method to do safely?

A. Insert arbitrary objects into the list

B. Read values as numeric values

C. Convert the list into a `List<Integer>`

D. Guarantee that every element is an Integer

Correct Answer: B. Read values as numeric values

Question 3

Why can a `TreeSet` unexpectedly discard an object that is not equal according to `equals`?

A. It uses insertion order instead of comparison

B. It treats objects that compare as zero as duplicates

C. It stores only primitive values

D. It automatically converts all objects to strings

Correct Answer: B. It treats objects that compare as zero as duplicates

Question 4

Which stream operation changes each input element into another representation?

A. filter

B. distinct

C. map

D. count

Correct Answer: C. map

Question 5

What is a major danger of adding elements to an external mutable list inside `stream().forEach(...)`?

A. The stream becomes a map

B. The operation necessarily sorts the list

C. It introduces uncontrolled side effects and possible concurrency problems

D. It prevents all elements from being read

Correct Answer: C. It introduces uncontrolled side effects and possible concurrency problems

Question 6

Which design best protects an object from later changes to a caller-supplied list?

A. Store the caller’s list reference directly

B. Store the list as a raw type

C. Copy the list using an immutable-copy operation

D. Convert the list to an iterator

Correct Answer: C. Copy the list using an immutable-copy operation

Question 7

A method only needs to retrieve values from a generic collection of numeric subtypes. Which declaration best expresses that requirement?

A. `List<? super Number>`

B. `List<? extends Number>`

C. `List<Object>` only

D. Raw `List`

Correct Answer: B. `List<? extends Number>`

Question 8

Which statement about stream intermediate operations is generally correct?

A. They always execute immediately

B. They describe computation that is usually evaluated when a terminal operation runs

C. They can be used repeatedly after a stream is consumed

D. They always create a new database table

Correct Answer: B. They describe computation that is usually evaluated when a terminal operation runs

Question 9

A catalogue requires lookup by product identifier and sorted display by rating. Which design is most suitable?

A. Only a linked list

B. A map for identity lookup and a comparator for display ordering

C. Only a priority queue, regardless of display requirements

D. A raw collection containing mixed objects

Correct Answer: B. A map for identity lookup and a comparator for display ordering

Question 10

Why should subtraction generally not be used directly to implement integer comparison?

A. It always produces floating-point values

B. It can overflow and produce an incorrect ordering

C. It removes duplicates automatically

D. It disables generic type checking

Correct Answer: B. It can overflow and produce an incorrect ordering