Я большой поклонник Алгебраических типов данных. Они позволяют нам декларативно указывать грамматику модели данных. Многие современные статически типизированные языки предоставляют эту функциональность из коробки, что позволяет писать очень выразительный код. Поскольку я в основном работаю с Java, я несколько раз пытался использовать ADT в Java. Это не было приятным опытом. Java просто не предоставляет подходящих инструментов. В прошлый раз, когда я пытался, это было с Java 11. Теперь, когда мы работаем с Java 15, я решил попробовать еще раз, используя новые функции.

Одной из основных структур данных, с которыми мы работаем, являются списки. При изучении функционального языка они обычно являются первым препятствием, которое требует времени, чтобы разобраться. В Haskell список в значительной степени определяется как:

data List a = Empty | Cons a (List a)

Это означает, что список либо пуст (без элементов), либо содержит элемент и указатель на следующий «объект». Короче говоря, это определение связанного списка. Довольно аккуратно, правда? Чтобы не показаться снобом Haskell, то же самое можно сделать в Typescript:

type List<T> = null | {value: T, next: List<T>}

Я попытался воссоздать это в Java 15 и придумал следующее:

Мы сделали здесь несколько новых вещей, которые раньше были невозможны.

Сначала у нас есть запечатанные классы (https://openjdk.java.net/jeps/360). Это классы/интерфейсы, которые строго определяют, какие классы могут от них наследоваться. Это означает, что когда мы проверяем тип объекта, мы можем сделать это исчерпывающе. Одним из основных критических замечаний по поводу использования instanceof является тот факт, что мы никогда не знаем, с какими реализациями мы можем столкнуться. До сих пор. Это позволяет нам безопасно доставлять больше логики через систему типов, позволяя компилятору проверить ее для нас.

Во-вторых, это записи (https://openjdk.java.net/jeps/384). Это позволяет нам объявлять неизменяемые модели данных с гораздо меньшим количеством шаблонов. Было бы здорово, если бы нам не нужны были эти фигурные скобки в конце :).

Итак, это определение LinkedList с использованием системы типов в Java 15. Давайте посмотрим на это в действии:

LinkedList<String> emptyList = new LinkedList.Nil<>();
System.out.println(emptyList);
LinkedList<String> oneElementList = new LinkedList.Cons<>("Test", new LinkedList.Nil<>());
System.out.println(oneElementList);

Давайте попробуем составить больший список. Для этого нам нужен метод util:

static <T> LinkedList<T> addElement(LinkedList<T> list, T element) {
    if (list instanceof Nil<T>) { 
        return new Cons<>(element, new Nil<>()); 
    } else if (list instanceof Cons<T> cons) { 
        return new Cons<>(cons.value, addElement(cons.next, element)); 
    } else { 
        throw new IllegalArgumentException("Unknown type"); 
    }
}

Здесь мы снова воспользуемся преимуществом новой функции Java: сопоставление шаблонов instanceof (https://openjdk.java.net/jeps/375). Это позволяет нам пропустить приведение типов после проверки instanceof, что делает код более читаемым. На самом деле, как только мы проделаем еще одну работу в этой области и получим запланированное выражение switch для instanceof, в итоге получится что-то вроде:

static <T> LinkedList<T> addElement(LinkedList<T> list, T element) {
    return switch (list) { 
        case Nil<T> nil -> new Cons<>(element, new Nil<>());
        case Cons<T> cons -> new Cons<>(cons.value, addElement(cons.next, element)); 
    } 
}

Что в итоге будет вполне приятно глазу. Мы можем использовать этот код так же просто, как:

LinkedList<Integer> list = new LinkedList.Nil<>(); 
for (int i = 0; i < 10; i++) { 
    list = addElement(list, i); 
}

Я добавил в решение еще несколько функций, а полный код можно найти здесь.

Вывод

Вот оно. Неизменяемый LinkedList, написанный с использованием системы типов. Есть еще место для улучшений, но я чувствую, что Java на правильном пути. Хотя эти функции все еще находятся в стадии предварительной версии, я очень надеюсь, что когда мы достигнем следующей LTS (Java 17?), мы сможем по-настоящему воспользоваться преимуществами методов ADT. Конечно, Java догоняет другие языки JVM, такие как Kotlin и Scala, но я надеюсь, что их реализация будет лучше, поскольку Java может играть с JVM по своему усмотрению. В следующий раз, когда кто-то попросит вас внедрить связанный список на собеседовании, вы можете просто использовать это :P.

Первоначально опубликовано на https://jpintelli.wordpress.com 28 декабря 2020 г.