The ListMonad:

Non-Deterministic Computation with Java Lists

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:

// Find all paths of length 2 from a starting node
List<List<String>> 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:

MonadZero<ListKind.Witness> listMonad = Instances.monadZero(list());
Kind<ListKind.Witness, String> starts = listMonad.of(start);

Kind<ListKind.Witness, String> step1 = listMonad.flatMap(
    node -> LIST.widen(neighbors(node)), starts);

Kind<ListKind.Witness, String> 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

How ap Produces a Cartesian Product

The ap operation applies every function to every value, producing all combinations:

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.

MonadZero<ListKind.Witness> listMonad = Instances.monadZero(list());

// --- Wrap a standard List into the Kind system ---
Kind<ListKind.Witness, Integer> numbers = LIST.widen(Arrays.asList(1, 2, 3, 4));

// --- Lift a single value into a singleton list ---
Kind<ListKind.Witness, String> single = listMonad.of("hello"); // ["hello"]
Kind<ListKind.Witness, Object> empty  = listMonad.of(null);    // []

// --- Unwrap back to a standard List ---
List<Integer> unwrapped = LIST.narrow(numbers); // [1, 2, 3, 4]

// --- map: transform every element ---
Kind<ListKind.Witness, String> decorated = listMonad.map(
    n -> "*" + n + "*", numbers);
// LIST.narrow(decorated) => ["*1*", "*2*", "*3*", "*4*"]

MonadZero<ListKind.Witness> listMonad = Instances.monadZero(list());
Kind<ListKind.Witness, Integer> values = LIST.widen(Arrays.asList(1, 2, 3));

// Each number branches into itself and itself + 10
Function<Integer, Kind<ListKind.Witness, Integer>> branch =
    i -> LIST.widen(Arrays.asList(i, i + 10));

Kind<ListKind.Witness, Integer> expanded = listMonad.flatMap(branch, values);
// [1, 11, 2, 12, 3, 13]

// Filtering: return an empty list to eliminate a branch
Function<Integer, Kind<ListKind.Witness, String>> evenOnly =
    i -> (i % 2 == 0)
        ? LIST.widen(Arrays.asList("even", String.valueOf(i)))
        : LIST.widen(List.of()); // empty — odd numbers are dropped

Kind<ListKind.Witness, String> filtered = listMonad.flatMap(evenOnly, values);
// ["even", "2"]

MonadZero<ListKind.Witness> listMonad = Instances.monadZero(list());

Function<Integer, String> addPrefix      = i -> "Val: " + i;
Function<Integer, String> multiplyString = i -> "Mul: " + (i * 2);

Kind<ListKind.Witness, Function<Integer, String>> functions =
    LIST.widen(Arrays.asList(addPrefix, multiplyString));
Kind<ListKind.Witness, Integer> inputs = LIST.widen(Arrays.asList(10, 20));

Kind<ListKind.Witness, String> results = listMonad.ap(functions, inputs);
// ["Val: 10", "Val: 20", "Mul: 20", "Mul: 40"]

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":

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<EitherPath<E, Node>> becomes an EitherPath<E, List<Node>>. 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 for the wider picture and Foldable & Traverse for what traverse is doing here.

When to Use ListMonad

./gradlew :hkj-benchmarks:jmh --includes=".*ListBenchmark.*"

Previous: Lazy Next: Maybe