NonEmptyList: A List That Is Never Empty

Hold a list that always has a first element, so reading it never throws.

NonEmptyList at a glance


Models	A list with at least one element
Replaces	A `List` checked with `isEmpty()` before `getFirst()`
Effect Path	None: a Path holds it, as `ValidationPath` holds its errors
Instances	`Functor`, `Applicative`, `Monad`, `Foldable`, `Traverse`
Choose it when	The list can never be empty, such as an invalid result's errors; otherwise List, or compare every type in Choosing a Type

What You'll Learn

Turn a list that may be empty into a NonEmptyList once, at the boundary
Total a list with reduce, and read its first or largest element, with nothing to guard
Say why List<String> is the wrong type for an invalid result's errors
Choose between NonEmptyList's ap and its semigroup() for combining two lists
Say why NonEmptyList has no empty value and no Monoid

See Example Code

The code on this page is NonEmptyListBook.java: the page includes it, so the build compiles and runs it. NonEmptyListBookTest.java holds what the page says each method does.

An order's lines

Code that reads the first element of a List, or totals it, must first check isEmpty(): getFirst() throws on an empty list, and a total needs a starting value. NonEmptyList<A> holds at least one element by its type, so the check happens once, where the list is made, and nowhere after.

The code on this page uses these imports, with Order and LineItem from the order records the Optics chapter introduces:

import java.math.BigDecimal;
import java.util.Comparator;
import java.util.List;
import org.higherkindedj.example.book.optics.cast.LineItem;
import org.higherkindedj.example.book.optics.cast.Order;
import org.higherkindedj.hkt.Monoids;
import org.higherkindedj.hkt.maybe.Maybe;
import org.higherkindedj.hkt.nonemptylist.NonEmptyList;
import org.higherkindedj.hkt.validated.Validated;

An order has a List of lines, and an order with none should not reach the code that totals it. NonEmptyList.fromList makes the check: it gives a Maybe, empty for an empty list. PLACED has two lines, and EMPTIED none:

  // An order with no lines gives Nothing, so the empty case is handled once, here
  static Maybe<NonEmptyList<LineItem>> lines(Order order) {
    return NonEmptyList.fromList(order.lines());
  }

    Maybe<NonEmptyList<LineItem>> placed = lines(PLACED);
    // Just(NonEmptyList[LineItem[sku=LAMP, quantity=2, price=40.00],
    //   LineItem[sku=SHADE, quantity=1, price=12.50]])
    Maybe<NonEmptyList<LineItem>> emptied = lines(EMPTIED);
    // Nothing

Past that check, the code needs no guard. reduce totals the lines with Monoids.bigDecimalAddition(), the book's way to add money, and uses only its join, never its empty value, because there is always a first line. max and head return a line, never an Optional:

  static BigDecimal lineTotal(LineItem line) {
    return line.price().multiply(BigDecimal.valueOf(line.quantity()));
  }

  // reduce uses only the monoid's join: there is always a first line to start from
  static BigDecimal orderTotal(NonEmptyList<LineItem> lines) {
    return lines.map(NonEmptyListBook::lineTotal).reduce(Monoids.bigDecimalAddition());
  }

  static LineItem priciest(NonEmptyList<LineItem> lines) {
    return lines.max(Comparator.comparing(NonEmptyListBook::lineTotal));
  }

Maybe's map runs them only on an order that has lines:

    Maybe<BigDecimal> total = placed.map(NonEmptyListBook::orderTotal);
    // Just(92.50)
    Maybe<LineItem> first = placed.map(NonEmptyList::head);
    // Just(LineItem[sku=LAMP, quantity=2, price=40.00])
    Maybe<LineItem> priciest = placed.map(NonEmptyListBook::priciest);
    // Just(LineItem[sku=LAMP, quantity=2, price=40.00])

The same code over a List would need a starting value for the total, such as BigDecimal.ZERO, and an Optional for the largest line.

Creating instances

Java has no literal for a list that is never empty, so each factory names where the first element comes from:

    NonEmptyList<String> skus = NonEmptyList.of("LAMP", "SHADE", "BULB");
    NonEmptyList<String> one = NonEmptyList.single("LAMP");
    NonEmptyList<String> joined = one.concat(NonEmptyList.of("SHADE")).append("BULB");
    // NonEmptyList[LAMP, SHADE, BULB]

fromList and fromIterable take data that may be empty, and give a Maybe rather than throwing. Every element is checked when the list is built, so a null is refused, as Values, never null says for every type.

As the error list

An invalid result always has at least one error, yet its errors are often held in a List, which can be empty. Nothing stops the impossible case being built:

    // An invalid result should hold at least one error, but a List can be empty
    Validated<List<String>, Order> noReason = Validated.invalid(List.of());
    // Invalid([])

noReason.getError().getFirst() throws NoSuchElementException. With a NonEmptyList as the error list, the impossible case cannot be built, and reading the first error needs no guard:

    Validated<NonEmptyList<String>, Order> refused = Validated.invalidNel("order has no lines");
    // Invalid(NonEmptyList[order has no lines])
    String firstReason = refused.getError().head();

Validated's validNel, invalidNel, accumulate() and fields() all hold the errors in a NonEmptyList, and Cats pairs its Validated with a NonEmptyList in the same way. accumulate() and fields() need no Semigroup argument. Neither does a ValidationPath built with Path.validNel or Path.invalidNel, which carries NonEmptyList.semigroup() with it. Validated's own ap, and Instances.validated, still take one: pass NonEmptyList.semigroup(), which joins two error lists end to end, so the errors keep the order the checks ran.

Methods

Method	What it does
`NonEmptyList.of(first, rest...)`, `single(a)`	Build a list from its first element and any others
`NonEmptyList.fromList(list)`, `fromIterable(items)`	Give a `Maybe`, empty for empty input
`head()`, `last()`	Return the first or last element
`tail()`	Returns the elements after the first, as a `List` that cannot be changed, possibly empty
`reduce(semigroup)`	Joins every element, with no starting value
`min(comparator)`, `max(comparator)`	Return the smallest or largest element
`map(f)`, `flatMap(f)`	Change each element, or replace each with a `NonEmptyList`
`concat(other)`, `append(a)`, `prepend(a)`	Join two lists, or add one element
`foldLeft(start, f)`, `reverse()`, `size()`	Fold from the left, reverse, or count
`stream()`, `toJavaList()`	Give a `Stream`, or a `List` that cannot be changed
`NonEmptyList.semigroup()`	Joins two lists end to end, keeping their order

NonEmptyList is also Iterable, so a for-each loop reads it directly.

Working with Kind

Generic code, written once for any container, takes NonEmptyList through its Monad instance, from Instances.monad(nonEmptyList()). The instance works over Kind<NonEmptyListKind.Witness, A>, so you widen a list to pass it in, and narrow the result to read it. These are the extra imports:

import static org.higherkindedj.hkt.instances.Witnesses.nonEmptyList;
import static org.higherkindedj.hkt.nonemptylist.NonEmptyListKindHelper.NON_EMPTY_LIST;

import java.util.function.Function;
import org.higherkindedj.hkt.Kind;
import org.higherkindedj.hkt.Monad;
import org.higherkindedj.hkt.instances.Instances;
import org.higherkindedj.hkt.nonemptylist.NonEmptyListKind;

    Monad<NonEmptyListKind.Witness> nonEmpty = Instances.monad(nonEmptyList());

    Kind<NonEmptyListKind.Witness, Function<BigDecimal, BigDecimal>> adjustments =
        NON_EMPTY_LIST.widen(
            NonEmptyList.of(
                price -> price.add(new BigDecimal("4.99")),
                price -> price.subtract(new BigDecimal("5.00"))));
    Kind<NonEmptyListKind.Witness, BigDecimal> prices =
        NON_EMPTY_LIST.widen(NonEmptyList.of(new BigDecimal("40.00"), new BigDecimal("12.50")));

    // ap pairs every adjustment with every price, as List's does
    NonEmptyList<BigDecimal> everyPairing = NON_EMPTY_LIST.narrow(nonEmpty.ap(adjustments, prices));
    // NonEmptyList[44.99, 17.49, 35.00, 7.50]

Two ways to combine

NonEmptyList.semigroup() joins two lists end to end: [a] and [b] give [a, b]. The instance's ap pairs every element of one with every element of the other, as List's does. Error lists are joined with the semigroup.

Widening allocates nothing: NonEmptyList implements NonEmptyListKind itself, so widen returns the same object. NonEmptyList has instances of other type classes too, such as Traverse, each an object of its own, and NonEmptyList at a glance, at the head of the page, lists them.

No empty, by design

No factory builds an empty NonEmptyList, so it has no Monoid instance and no Alternative or MonadZero. Each of those needs an empty value, which would bring back the case the type exists to rule out. NonEmptyList.semigroup() joins two lists, but nothing gives a Monoid's empty one.

When to use `NonEmptyList`

You need	Use
A list that can never be empty, such as an invalid result's errors	`NonEmptyList`
A list that may be empty	List
The errors of independent checks, kept together	Validated, whose `invalidNel` holds them in a `NonEmptyList`
A record built from many checked fields	Accumulating Assembly

Previous: EitherOrBoth Next: Maybe

Higher-Kinded-J: Composable Effects and Advanced Optics for Java