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;
        };
    }

    default List<T> prepend(T element) {
        return new NonEmpty<>(element, this);
    }

    default List<T> append(T element) {
        return switch (this) {
            case NonEmpty<T>(var head, var tail)
                -> new NonEmpty<>(head, tail.append(element));
            case Empty<T> _ -> new NonEmpty<>(element, this);
        };
    }

    @SafeVarargs
    static <T> List<T> of(T...values) {
        List<T> list = empty();
        for (T value : values) {
            list = list.append(value);
        }
        return list;
    }

    static <T> List<T> list(T head, List<T> tail) {
        return new NonEmpty<T>(head, tail);
    }

    static <T> List<T> empty() {
        return new Empty<T>();
    }

    static void main() {
        var list = list(1, list(2, list(3, empty())));
        var result = list.fold(0, Integer::sum);
        System.out.println(result);
    }
}