import java.util.function.BinaryOperator;
import java.util.function.Function;
import java.util.function.Predicate;

sealed interface List<T> {

    record NonEmpty<T>(T head, List<T> tail) implements List<T> {}
    record Empty<T>() implements List<T> {}

    default <R> List<R> map(Function<T, R> mapper) {
        return switch (this) {
            case NonEmpty<T>(var head, var tail)
                -> new NonEmpty<>(mapper.apply(head), tail.map(mapper));
            case Empty<T>()
                -> new Empty<>();
        };
    }

    default List<T> filter(Predicate<T> filter) {
        return switch (this) {
            case NonEmpty<T>(var head, var tail) when filter.test(head)
                -> new NonEmpty<>(head, tail.filter(filter));
            case NonEmpty<T>(var head, var tail)
                -> tail.filter(filter);
            case Empty<T>()
                -> new Empty<>();
        };
    }

    default T fold(T initial, BinaryOperator<T> operator) {
        return switch (this) {
            case NonEmpty<T>(var head, var tail)
                -> tail.fold(operator.apply(initial, head), operator);
            case Empty<T>() -> initial;
        };
    }
}