# The ListMonad: ## _Non-Deterministic Computation with Java Lists_ ~~~admonish info title="What You'll Learn" - How to model non-deterministic computations where each step produces multiple results - Using `flatMap` to explore all combinations and `ap` to produce Cartesian products - Building search algorithms and combinatorial problems with monadic operations - Generating and filtering results within the higher-kinded type system ~~~ ~~~ admonish example title="See Example Code:" [ListMonadExample.java](https://github.com/higher-kinded-j/higher-kinded-j/blob/main/hkj-examples/src/main/java/org/higherkindedj/example/basic/list/ListMonadExample.java) ~~~ ## The Problem: Non-Deterministic Computation Some computations don't have a single answer; they have many. Consider finding all valid moves for a chess piece, all paths through a grid, or all ways to make change for a dollar. In each case, every intermediate step branches into multiple possibilities, and you need to explore *all* of them. With plain Java, this means nested loops, manual concatenation, and tangled control flow: ```java // Find all paths of length 2 from a starting node List> paths = new ArrayList<>(); for (String first : neighbors(start)) { for (String second : neighbors(first)) { paths.add(List.of(start, first, second)); } } ``` Each level of nesting adds another loop. If the number of steps is dynamic, you need recursion with manual list-building. The structure of the problem ("for each possibility, explore further") is buried under bookkeeping. The `ListMonad` captures this pattern directly. A `List` represents multiple possible values, `flatMap` explores all combinations by applying a function to each element and concatenating the results, and `ap` produces Cartesian products. The nested-loop problem above becomes: ```java MonadZero listMonad = Instances.monadZero(list()); Kind starts = listMonad.of(start); Kind step1 = listMonad.flatMap( node -> LIST.widen(neighbors(node)), starts); Kind step2 = listMonad.flatMap( node -> LIST.widen(neighbors(node)), step1); // step2 contains every node reachable in exactly 2 hops ``` Each `flatMap` expands one level of the search tree. No nested loops, no manual concatenation; the monad handles it. ## Core Components | Component | Role | |-----------|------| | `List` | Standard Java list, the underlying data structure | | `ListKind` / `ListKindHelper` | HKT bridge: `widen()` wraps a `List` into `Kind`, `narrow()` unwraps it back | | `ListMonad` | `Monad`: provides `map`, `flatMap`, `of`, and `ap` over lists | ~~~admonish note title="How the Operations Map" The monad operations correspond to familiar list operations: | Type Class Operation | What It Does | |---------------------|--------------| | `listMonad.of(value)` | Create a singleton list containing `value` (`null` produces an empty list) | | `listMonad.map(f, fa)` | Apply `f` to every element, same as `stream().map(f).toList()` | | `listMonad.flatMap(f, fa)` | Apply `f` to each element (where `f` returns a list), concatenate all results, same as `stream().flatMap(...)` | | `listMonad.ap(ff, fa)` | Apply every function in `ff` to every value in `fa`: Cartesian product | The key insight: `flatMap` on lists *is* non-deterministic computation. Each element branches into zero or more results, and all branches are collected into a single list. ~~~ ### How `ap` Produces a Cartesian Product The `ap` operation applies *every* function to *every* value, producing all combinations: ```text functions: [f1, f2] values: [a, b, c] ↓ ap ↓ results: [f1(a), f1(b), f1(c), f2(a), f2(b), f2(c)] ``` This is the applicative Cartesian product. If you have `n` functions and `m` values, `ap` produces `n * m` results. ## Working with ListMonad The following examples demonstrate creating list contexts, composing operations, and building combinatorial pipelines. ~~~admonish example title="Creating Instances and Basic Operations" - [ListMonadExample.java](https://github.com/higher-kinded-j/higher-kinded-j/blob/main/hkj-examples/src/main/java/org/higherkindedj/example/basic/list/ListMonadExample.java) ```java MonadZero listMonad = Instances.monadZero(list()); // --- Wrap a standard List into the Kind system --- Kind numbers = LIST.widen(Arrays.asList(1, 2, 3, 4)); // --- Lift a single value into a singleton list --- Kind single = listMonad.of("hello"); // ["hello"] Kind empty = listMonad.of(null); // [] // --- Unwrap back to a standard List --- List unwrapped = LIST.narrow(numbers); // [1, 2, 3, 4] // --- map: transform every element --- Kind decorated = listMonad.map( n -> "*" + n + "*", numbers); // LIST.narrow(decorated) => ["*1*", "*2*", "*3*", "*4*"] ``` ~~~ ~~~admonish example title="Composing with flatMap: Exploring All Combinations" - [ListMonadExample.java](https://github.com/higher-kinded-j/higher-kinded-j/blob/main/hkj-examples/src/main/java/org/higherkindedj/example/basic/list/ListMonadExample.java) `flatMap` is where the non-deterministic power lives. Each element branches into multiple results, and all branches are collected. ```java MonadZero listMonad = Instances.monadZero(list()); Kind values = LIST.widen(Arrays.asList(1, 2, 3)); // Each number branches into itself and itself + 10 Function> branch = i -> LIST.widen(Arrays.asList(i, i + 10)); Kind expanded = listMonad.flatMap(branch, values); // [1, 11, 2, 12, 3, 13] // Filtering: return an empty list to eliminate a branch Function> evenOnly = i -> (i % 2 == 0) ? LIST.widen(Arrays.asList("even", String.valueOf(i))) : LIST.widen(List.of()); // empty: odd numbers are dropped Kind filtered = listMonad.flatMap(evenOnly, values); // ["even", "2"] ``` ~~~ ~~~admonish example title="Cartesian Products with ap" - [ListMonadExample.java](https://github.com/higher-kinded-j/higher-kinded-j/blob/main/hkj-examples/src/main/java/org/higherkindedj/example/basic/list/ListMonadExample.java) `ap` applies a list of functions to a list of values, producing every combination. ```java MonadZero listMonad = Instances.monadZero(list()); Function addPrefix = i -> "Val: " + i; Function multiplyString = i -> "Mul: " + (i * 2); Kind> functions = LIST.widen(Arrays.asList(addPrefix, multiplyString)); Kind inputs = LIST.widen(Arrays.asList(10, 20)); Kind results = listMonad.ap(functions, inputs); // ["Val: 10", "Val: 20", "Mul: 20", "Mul: 40"] ``` This is the same Cartesian product shown in the diagram above: 2 functions applied to 2 values yields 4 results. ~~~ --- ## Back to the One-Liner `List` does not appear in the Foundations one-liner because that line operates on a single record. The shape changes as soon as the request is "do this for every item": ```java LIST.widen(repo.findAll(query)) .traverse(eitherApplicative, node -> Path.either(node) .focus().attributes().at(key) .modify(spec::validateAndCoerce) .flatMap(repo::save)); ``` `List`'s role here is the structure being walked; `traverse` flips it inside out so a `List>` becomes an `EitherPath>`. The same focus / modify / save skeleton runs once per item, and the whole batch either succeeds or surfaces the first failure. `ListMonad` is what makes `List` participate in `traverse` and the rest of the generic combinators. See [One Line, Six Layers](../hkts/one_line_six_layers.md) for the wider picture and [Foldable & Traverse](../functional/foldable_and_traverse.md) for what `traverse` is doing here. ## When to Use ListMonad | Scenario | Use | |----------|-----| | Non-deterministic computation, exploring all possibilities | `ListMonad` with `flatMap` to branch and collect | | Generating combinations or Cartesian products | `ListMonad` with `ap` | | Writing generic code that works across monads | `ListMonad`: your logic programs against `Kind` | | Filtering within a pipeline (guard-style) | Return empty lists from `flatMap` to prune branches | | Single-value computation with optionality | Prefer [Maybe](maybe_monad.md) instead | ~~~admonish important title="Key Points" - `ListMonad` implements `Monad`, giving you `map`, `flatMap`, `of`, and `ap` over standard Java lists. - `flatMap` is non-deterministic composition: each element can produce zero, one, or many results, and all results are concatenated. - `ap` produces the Cartesian product of a list of functions and a list of values, O(n*m) results. - `of(null)` produces an empty list, not a singleton containing `null`. - For the HKT bridge: `LIST.widen()` wraps a `List` into `Kind`, `LIST.narrow()` unwraps it back. Both are low-cost cast operations. ~~~ ~~~admonish example title="Benchmarks" List has dedicated JMH benchmarks measuring map, flatMap, and ap composition. Key expectations: - **`map`** scales linearly with list size - **`flatMap`** performance depends on the output size of the mapping function - **`ap`** produces Cartesian products, O(n*m) where n = functions, m = values ```bash ./gradlew :hkj-benchmarks:jmh --includes=".*ListBenchmark.*" ``` See [Benchmarks & Performance](../benchmarks.md) for full details. ~~~ --- **Previous:** [Lazy](lazy_monad.md) **Next:** [NonEmptyList](nonemptylist_monad.md)