Статьи

Функциональные структуры данных в Java 8 с Javaslang

Февраль 24, 2019

Лямбда в Java 8 (λ) дает нам возможность создавать прекрасные API. Они невероятно увеличивают выразительность языка.

Javaslang использовал лямбды для создания различных новых функций на основе функциональных шаблонов. Одна из них — это функциональная библиотека коллекций, предназначенная для замены стандартных коллекций Java.

(Это просто вид с высоты птичьего полета, ниже вы найдете удобочитаемую версию.)

(Это просто вид с высоты птичьего полета, ниже вы найдете удобочитаемую версию.)

Функциональное программирование

Прежде чем мы углубимся в детали структур данных, я хочу поговорить о некоторых основах. Это прояснит, почему я создал Javaslang и особенно новые коллекции Java.

Побочные эффекты

Java-приложения обычно имеют множество побочных эффектов . Они видоизменяют какое-то состояние, может быть, внешний мир. Распространенными побочными эффектами являются изменение объектов или переменных на месте , печать на консоль, запись в файл журнала или в базу данных. Побочные эффекты считаются вредными, если они влияют на семантику нашей программы нежелательным образом.

Например, если функция выдает исключение, и это исключение интерпретируется , это рассматривается как побочный эффект, который влияет на нашу программу . Кроме того, исключения похожи на нелокальные операторы goto . Они нарушают нормальный поток управления. Тем не менее, реальные приложения имеют побочные эффекты.

1
2
3
4
int divide(int dividend, int divisor) {
    // throws if divisor is zero
    return dividend / divisor;
}

В функциональной обстановке мы находимся в благоприятной ситуации, чтобы инкапсулировать побочный эффект в Try:

1
2
3
4
// = Success(result) or Failure(exception)
Try<Integer> divide(Integer dividend, Integer divisor) {
    return Try.of(() -> dividend / divisor);
}

Эта версия деления больше не выбрасывает. Мы сделали возможный сбой явным, используя тип Try.

Марио Фуско-Изменчивость

Ссылочная прозрачность

Функция, или более общее выражение, называется ссылочно-прозрачной, если вызов может быть заменен его значением, не влияя на поведение программы. Проще говоря, при одинаковом входе выход всегда одинаков.

1
2
3
4
5
// not referential transparent
Math.random();
 
// referential transparent
Math.max(1, 2);

Функция называется чистой, если все используемые выражения являются ссылочно-прозрачными. Приложение, состоящее из чистых функций, скорее всего, просто будет работать, если оно скомпилируется. Мы можем рассуждать об этом. Модульные тесты легко написать, а отладка становится пережитком прошлого.

Мышление в ценностях

Рич Хики, создатель Clojure, выступил с великолепной речью о ценности . Самые интересные значения — это неизменные значения. Основная причина в том, что неизменные ценности

  • по своей сути потокобезопасны и, следовательно, не нуждаются в синхронизации
  • стабильны в отношении equals и hashCode и, таким образом, являются надежными хеш-ключами
  • не нужно клонировать
  • вести себя безопасно для типов при использовании в непроверенных ковариантных приведениях (специфичных для Java)

Ключом к лучшему Java является использование неизменяемых значений в паре со ссылочными прозрачными функциями .

Javaslang предоставляет необходимые элементы управления и коллекции для достижения этой цели в повседневном программировании на Java.

Структуры данных в двух словах

Библиотека коллекций Javaslang состоит из богатого набора функциональных структур данных, построенных поверх лямбд. Единственный интерфейс, которым они делятся с оригинальными коллекциями Java, — это Iterable. Основная причина в том, что методы-мутаторы интерфейсов коллекции Java не возвращают объект базового типа коллекции.

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

Изменяемые структуры данных

Java — это объектно-ориентированный язык программирования. Мы инкапсулируем состояние в объектах для достижения сокрытия данных и предоставляем методы-мутаторы для управления состоянием. Инфраструктура коллекций Java (JCF) построена на этой идее.

1
2
3
4
interface Collection<E> {
    // removes all elements from this collection
    void clear();
}

Сегодня я воспринимаю пустое возвращение как запах. Это свидетельствует о том, что побочные эффекты имеют место, состояние мутировало. Общее изменяемое состояние является важным источником сбоев, причем не только при одновременной настройке.

Неизменяемые структуры данных

Неизменяемые структуры данных не могут быть изменены после их создания. В контексте Java они широко используются в виде упаковщиков коллекций.

1
2
3
4
List<String> list = Collections.unmodifiableList(otherList);
 
// Boom!
list.add("why not?");

Существуют различные библиотеки, которые предоставляют нам аналогичные служебные методы. Результатом всегда является неизменяемое представление конкретной коллекции. Обычно он генерирует во время выполнения, когда мы вызываем метод мутатора.

Постоянные структуры данных

Постоянная структура данных сохраняет свою предыдущую версию при изменении и поэтому является практически неизменной. Полностью постоянные структуры данных позволяют выполнять обновления и запросы для любой версии.

Многие операции выполняют только небольшие изменения. Простое копирование предыдущей версии не будет эффективным. Чтобы сэкономить время и память, важно идентифицировать сходства между двумя версиями и обмениваться как можно большим количеством данных.

Эта модель не навязывает никаких деталей реализации. Здесь приходят функциональные структуры данных в игру.

Функциональные структуры данных

Также известные как чисто функциональные структуры данных , они неизменны и постоянны . Методы функциональных структур данных являются ссылочно-прозрачными .

Javaslang обладает широким спектром наиболее часто используемых функциональных структур данных. Следующие примеры подробно объясняются.

Связанный список

Одной из самых популярных и простых функциональных структур данных является (по отдельности) связанный список . Он имеет головной элемент и хвостовой список. Связанный список ведет себя как стек, который следует за методом « последний вошел — первым вышел» (LIFO) .

В Javaslang мы создаем экземпляр List следующим образом:

1
2
// = List(1, 2, 3)
List<Integer> list1 = List.of(1, 2, 3);

Каждый из элементов списка образует отдельный узел списка. Хвост последнего элемента — ноль, пустой список.

песни1

Это позволяет нам совместно использовать элементы в разных версиях Списка.

1
2
// = List(0, 2, 3)
List<Integer> list2 = list1.tail().prepend(0);

Новый головной элемент 0 связан с хвостом исходного списка. Первоначальный список остается неизменным.

песни2

Эти операции выполняются в постоянное время, другими словами, они не зависят от размера списка. Большинство других операций занимают линейное время. В Javaslang это выражается интерфейсом LinearSeq, который мы, возможно, уже знаем из Scala.

Если нам нужны структуры данных, которые можно запрашивать в постоянном времени, Javaslang предлагает Array и Vector. Оба имеют возможности произвольного доступа .

Тип Array поддерживается массивом объектов Java. Операции вставки и удаления занимают линейное время. Вектор находится между массивом и списком. Он хорошо работает в обеих областях, произвольного доступа и модификации.

Фактически связанный список может также использоваться для реализации структуры данных очереди.

Очередь

Очень эффективная функциональная очередь может быть реализована на основе двух связанных списков. Передний список содержит элементы в очереди , задний список содержит элементы в очереди . Обе операции enqueue и dequeue выполняют в O (1).

1
2
3
Queue<Integer> queue = Queue.of(1, 2, 3)
                            .enqueue(4)
                            .enqueue(5);

Начальная очередь состоит из трех элементов. Два элемента поставлены в очередь в заднем списке.

queue1

Если в переднем списке заканчивается количество элементов при снятии очереди, задний список переворачивается и становится новым передним списком.

queue2

При снятии очереди с элемента мы получаем пару первого элемента и оставшуюся очередь. Необходимо вернуть новую версию очереди, поскольку функциональные структуры данных являются неизменными и постоянными. Исходная очередь не затрагивается.

1
2
3
4
5
Queue<Integer> queue = Queue.of(1, 2, 3);
 
// = (1, Queue(2, 3))
Tuple2<Integer, Queue<Integer>> dequeued =
        queue.dequeue();

Что происходит, когда очередь пуста? Затем dequeue () сгенерирует исключение NoSuchElementException. Чтобы сделать это функциональным способом, мы предпочли бы получить дополнительный результат.

1
2
3
4
5
// = Some((1, Queue()))
Queue.of(1).dequeueOption();
 
// = None
Queue.empty().dequeueOption();

Необязательный результат может быть дополнительно обработан, независимо от того, пуст он или нет.

01
02
03
04
05
06
07
08
09
10
11
12
13
14
// = Queue(1)
Queue<Integer> queue = Queue.of(1);
 
// = Some((1, Queue()))
Option<Tuple2<Integer, Queue<Integer>>>
        dequeued = queue.dequeueOption();
 
// = Some(1)
Option<Integer> element =
        dequeued.map(Tuple2::_1);
 
// = Some(Queue())
Option<Queue<Integer>> remaining =
        dequeued.map(Tuple2::_2);

Сортированный набор

Сортированные наборы — это структуры данных, которые используются чаще, чем очереди. Мы используем двоичные деревья поиска для их функционального моделирования. Эти деревья состоят из узлов с двумя дочерними элементами и значениями в каждом узле.

Мы строим бинарные деревья поиска при наличии порядка, представленного элементом Comparator. Все значения левого поддерева любого данного узла строго меньше, чем значение данного узла. Все значения правого поддерева строго больше.

1
2
3
// = TreeSet(1, 2, 3, 4, 6, 7, 8)
SortedSet<Integer> xs =
        TreeSet.of(6, 1, 3, 2, 4, 7, 8);

binarytree1

Поиски на таких деревьях выполняются за O (log n). Мы начинаем поиск в корне и решаем, нашли ли мы элемент. Из-за общего порядка значений мы знаем, где искать дальше, в левой или в правой ветви текущего дерева.

1
2
3
4
5
6
7
// = TreeSet(1, 2, 3);
SortedSet<Integer> set = TreeSet.of(2, 3, 1, 2);
 
// = TreeSet(3, 2, 1);
Comparator<Integer> c = (a, b) -> b - a;
SortedSet<Integer> reversed =
        TreeSet.of(c, 2, 3, 1, 2);

Большинство операций с деревьями по своей природе являются рекурсивными . Функция вставки ведет себя подобно функции поиска. Когда достигается конец пути поиска, создается новый узел и весь путь восстанавливается до корня. На существующие дочерние узлы ссылаются всякий раз, когда это возможно. Следовательно, операция вставки занимает O (log n) время и пространство.

1
2
// = TreeSet(1, 2, 3, 4, 5, 6, 7, 8)
SortedSet<Integer> ys = xs.add(5);

binarytree2

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

В Javaslang мы реализовали двоичное дерево поиска на основе красного / черного дерева . Он использует особую стратегию окраски, чтобы сохранить дерево сбалансированным при вставках и удалениях. Чтобы узнать больше об этой теме, обратитесь к книге Криса Окасаки « Чисто функциональные структуры данных ».

Состояние коллекций

Как правило, мы наблюдаем сближение языков программирования. Хорошие особенности делают это, другие исчезают. Но Java отличается, она всегда будет обратно совместимой. Это сила, но она также замедляет эволюцию.

Лямбда сблизил Яву и Скалу, но они все еще такие разные. Мартин Одерски, создатель Scala, недавно упомянул в своем BDSBTB 2015 о состоянии коллекций Java 8.

Он описал поток Java как причудливую форму итератора. Java 8 Stream API является примером поднятой коллекции. Что он делает, так это определяет вычисление и связывает его с определенной коллекцией на другом явном шаге.

1
2
3
4
// i + 1
i.prepareForAddition()
 .add(1)
 .mapBackToInteger(Mappers.toInteger())

Вот как работает новый Java 8 Stream API. Это вычислительный уровень над известными коллекциями Java.

1
2
3
4
5
// = ["1", "2", "3"] in Java 8
Arrays.asList(1, 2, 3)
      .stream()
      .map(Object::toString)
      .collect(Collectors.toList())

Javaslang очень вдохновлен Scala. Вот как вышеприведенный пример должен был быть в Java 8.

1
2
// = Stream("1", "2", "3") in Javaslang
Stream.of(1, 2, 3).map(Object::toString)

В течение последнего года мы приложили много усилий для реализации библиотеки коллекций Javaslang. Он включает в себя наиболее широко используемые типы коллекций.

Seq

Мы начали наше путешествие с внедрения последовательных типов. Мы уже описали связанный список выше. Стрим, ленивый связанный список, следовал. Это позволяет нам обрабатывать возможно бесконечные длинные последовательности элементов.

коллекции-сл

Все коллекции являются Iterable и, следовательно, могут использоваться в расширенных операторах for.

1
2
3
for (String s : List.of("Java", "Advent")) {
    // side effects and mutation
}

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

1
2
3
List.of("Java", "Advent").forEach(s -> {
    // side effects and mutation
});

В любом случае, как мы уже видели, мы предпочитаем выражения, которые возвращают значение, а не операторы, которые ничего не возвращают. Посмотрев на простой пример, мы скоро поймем, что операторы добавляют шум и делят то, что принадлежит друг другу.

01
02
03
04
05
06
07
08
09
10
String join(String... words) {
    StringBuilder builder = new StringBuilder();
    for(String s : words) {
        if (builder.length() > 0) {
            builder.append(", ");
        }
        builder.append(s);
    }
    return builder.toString();
}

Коллекции Javaslang предоставляют нам множество функций для работы с базовыми элементами. Это позволяет нам выражать вещи очень кратко.

1
2
3
4
5
String join(String... words) {
    return List.of(words)
               .intersperse(", ")
               .fold("", String::concat);
}

Большинство целей могут быть достигнуты различными способами с помощью Javaslang. Здесь мы сократили все тело метода до быстрых вызовов функций в экземпляре List. Мы могли бы даже удалить весь метод и напрямую использовать наш список для получения результата вычисления.

1
List.of(words).mkString(", ");

В реальных приложениях мы теперь можем значительно сократить количество строк кода и, следовательно, снизить риск ошибок.

Установить и карта

Последовательности отличные. Но чтобы быть полным, библиотека коллекций также нуждается в различных типах Наборов и Карт.

Коллекции посаженные-карта

Мы описали, как моделировать отсортированные множества с бинарными древовидными структурами. Сортированная Карта — это не что иное, как отсортированный Набор, содержащий пары ключ-значение и имеющий порядок для ключей.

Реализация HashMap поддерживается Hash Array Mapped Trie (HAMT) . Соответственно, HashSet поддерживается HAMT, содержащим пары ключ-ключ.

Наша карта не имеет специального типа Entry для представления пар ключ-значение. Вместо этого мы используем Tuple2, который уже является частью Javaslang. Поля кортежа перечислены.

1
2
3
4
5
// = (1, "A")
Tuple2<Integer, String> entry = Tuple.of(1, "A");
 
Integer key = entry._1;
String value = entry._2;

Карты и кортежи используются по всему Javaslang. Кортежи неизбежны для обработки многозначных возвращаемых типов в общем виде.

1
2
3
4
5
// = HashMap((0, List(2, 4)), (1, List(1, 3)))
List.of(1, 2, 3, 4).groupBy(i -> i % 2);
 
// = List((a, 0), (b, 1), (c, 2))
List.of('a', 'b', 'c').zipWithIndex();

В Javaslang мы исследуем и тестируем нашу библиотеку, внедряя 99 задач Эйлера . Это отличное доказательство концепции. Пожалуйста, не стесняйтесь посылать запросы.

Руки вверх!

Я очень надеюсь, что эта статья вызвала у вас интерес к Javaslang. Даже если вы используете Java 7 (или ниже) на работе, как и я, можно следовать идее функционального программирования. Это будет очень хорошо!

Пожалуйста, убедитесь, что Javaslang является частью вашего toolbelt в 2016 году.

Счастливого взлома!

PS: вопрос? @_Javaslang или чат Gitter

Ссылка: Функциональные структуры данных в Java 8 с Javaslang от нашего партнера JCG Дэниела Дитриха в блоге Java Advent Calendar .
42
Share: