Функциональные / неизменяемые структуры данных для JVM?

Кто-нибудь знает библиотеку структуры данных Java / JVM, предоставляющую функциональные (или неизменяемые или «постоянные» в функциональном смысле) эквиваленты знакомых структур данных Java?

Под «функциональным» я подразумеваю, что сами объекты неизменяемы, в то время как модификации этих объектов возвращают новые объекты, совместно использующие те же внутренние элементы, что и родительский объект (для эффективности как времени, так и пространства; наивная реализация может просто скопировать все это на каждая запись).

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

Исключительные и постоянные структуры данных Clojure были извлечены как библиотека Java. Их можно найти по адресу http://github.com/krukow/clj-ds . Эти структуры данных не зависят от времени выполнения Clojure и поэтому могут использоваться без clojure.jar в пути к clojure.jar приложения. Они были созданы для бесперебойной работы с Java-кодом.

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

На странице github нет загрузочной банки. Вам нужно будет проверить источник и построить банку самостоятельно.

Функциональные и неизменяемые являются основными свойствами большинства библиотек коллекции Scala. Scala компилируется в JVM и хорошо взаимодействует с Java. Синтаксис Scala также намного ближе к Java, чем что-то вроде Clojure (синтаксис Lisp).

Вот интро-страница для API коллекции Scala. http://www.scala-lang.org/docu/files/collections-api/collections.html

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

Попробуйте использовать Guava , он имеет неизменяемую карту, список, набор. Он также имеет некоторые утилиты для поддержки неизменяемой коллекции, которая вместо этого модифицирует базовый объект, возвращает новый объект.

Я могу понять, почему classы параллелизма трудны для написания: очень легко получить там труднодоступные ошибки.

У Java есть хороший способ избежать таких ошибок при записи неизменяемых classов Collection : каждый вид Collection имеет метод, похожий на java.util.Collections.unmodifiableSet(someSet) , который предоставит вам обертку, которая позволит вам увидеть базовую Collection но блокирует все методы мутации. Это всего лишь обертка: вы все равно можете изменить базовую Collection если вы держите ссылку на нее лежащей, поэтому не делайте этого. Кроме того, немедленно клонируйте и оберните любую Collection которая поступает извне, потому что программисты, которые их передали, могут позже их модифицировать, изменяя ваши хорошие неизменные данные.


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

Я сделал абстрактный суперclass, спустив список API для Set (не забывая toString ). Для методов без отключения я просто передаю их базовому набору. Для методов mutating я бросаю UnsupportedOperationException и предоставляет альтернативные методы функционального стиля.

Вот этот абстрактный class, FunctionalSet :

 import java.util.Collections; import java.util.Collection; import java.util.Set; import java.util.HashSet; import java.util.Iterator; public abstract class FunctionalSet implements Set { // final to prevent mutations through reassignment. protected final Set set; // private to prevent any use of the default constructor. private FunctionalSet() { this.set = null; } // unmodifiableSet to prevent mutations through Iterator and in subclasses. protected FunctionalSet(final Set set) { this.set = Collections.unmodifiableSet(set); } public abstract FunctionalSet clone(); public abstract FunctionalSet fAdd(final E element); public abstract FunctionalSet fAddAll(final Collection elements); public abstract FunctionalSet fRemove(final Object element); public abstract FunctionalSet fRemoveAll(final Collection elements); public abstract FunctionalSet fRetainAll(final Collection elements); protected abstract FunctionalSet newFSet(final Set newSet); protected abstract Set newSet(); protected abstract Set cloneSet(); protected final FunctionalSet __fAdd(final E element) { if (set.contains(element)) return this; final Set newSet = cloneSet(); newSet.add(element); return newFSet(newSet); } protected final FunctionalSet __fAddAll(final Collection elements) { if (set.containsAll(elements)) return this; final Set newSet = cloneSet(); newSet.addAll(elements); return newFSet(newSet); } protected final FunctionalSet __fRemove(final Object element) { if (!set.contains(element)) return this; final Set newSet = cloneSet(); newSet.remove(element); return newFSet(newSet); } protected final Set __fRemoveAll(final Collection elements) { boolean hasNone = true; for (final Object element : elements) { if (set.contains(element)) { hasNone = false; break; } } if (hasNone) return this; final Set newSet = cloneSet(); newSet.removeAll(elements); return newFSet(newSet); } @SuppressWarnings("unchecked") protected final Set __fRetainAll(final Collection rawElements) { final Set elements = rawElements instanceof Set ? (Set) rawElements : new HashSet(rawElements); // If set is a subset of elements, we don't remove any of the elements. if (set.size() <= elements.size() && elements.containsAll(set)) return this; final Set newSet = newSet(); for (final E element : set) { if (elements.contains(element)) newSet.add(element); } return newFSet(newSet); } private final UnsupportedOperationException unsupported(final String call, final String goodCall) { return new UnsupportedOperationException( String.format(this.getClass().getName() + "s are immutable. Use %s instead of %s.", goodCall, call) ); } public final boolean add(final E element) { throw unsupported("add", "fAdd"); } public final boolean addAll(final Collection elements) { throw unsupported("addAll", "fAddAll"); } public final void clear() { throw unsupported("clear", "new " + this.getClass().getName() + "()"); } public final boolean remove(final Object element) { throw unsupported("remove", "fRemove"); } public final boolean removeAll(final Collection elements) { throw unsupported("removeAll", "fRemoveAll"); } public final boolean retainAll(final Collection elements) { throw unsupported("retainAll", "fRetainAll"); } public final boolean contains(final Object element) { return set.contains(element); } public final boolean containsAll(final Collection elements) { return set.containsAll(elements); } public final boolean equals(final Object object) { return set.equals(object); } public final int hashCode() { return set.hashCode(); } public final boolean isEmpty() { return set.isEmpty(); } public final Iterator iterator() { return set.iterator(); } public final int size() { return set.size(); } public final Object[] toArray() { return set.toArray(); } public final  E[] toArray(final E[] irrelevant) { return set.toArray(irrelevant); } public final String toString() { return set.toString(); } } 

В реализации очень мало дел. Я поставляю несколько конструкторов и методов утилиты и просто использую стандартные реализации всех методов мутирования.

Вот реализация, FunctionalHashSet . :

 import java.util.Collection; import java.util.Set; import java.util.HashSet; public final class FunctionalHashSet extends FunctionalSet implements Cloneable { public static final FunctionalHashSet EMPTY = new FunctionalHashSet(); public FunctionalHashSet() { super(new HashSet()); } public FunctionalHashSet(final HashSet set) { this(set, true); } @SuppressWarnings("unchecked") private FunctionalHashSet(final HashSet set, final boolean clone) { super(clone ? (HashSet) set.clone() : set); } public FunctionalHashSet(final Collection elements) { this(new HashSet(elements)); } protected FunctionalHashSet newFSet(final Set newSet) { return new FunctionalHashSet((HashSet) newSet, false); } protected HashSet newSet() { return new HashSet(); } @SuppressWarnings("unchecked") protected HashSet cloneSet() { return new HashSet(set); } public FunctionalHashSet clone() { return this; } public FunctionalHashSet fAdd(final E element) { return (FunctionalHashSet) __fAdd(element); } public FunctionalHashSet fAddAll(final Collection elements) { return (FunctionalHashSet) __fAddAll(elements); } public FunctionalHashSet fRemove(final Object element) { return (FunctionalHashSet) __fRemove(element); } public FunctionalHashSet fRemoveAll(final Collection elements) { return (FunctionalHashSet) __fRemoveAll(elements); } public FunctionalHashSet fRetainAll(final Collection elements) { return (FunctionalHashSet) __fRetainAll(elements); } } 

Несколько примечаний:

  • В каждом отдельном методе функциональной мутации я проверяю, будут ли вообще какие-либо изменения. Если нет, я просто возвращаю тот же самый FunctionalSet .
  • В clone я просто возвращаю тот же самый FunctionalSet
  • Запуск set через java.util.Collections.unmodifiableSet и объявление его final предотвращает два источника мутации: пользователи не могут мутировать через Iterator и разработчики не могут случайно мутировать в своих реализациях.

Вы можете принять это и немного изменить его для поддержки других Collection .

Коллекции Java, возможно, не столь неизменны, как вам бы хотелось, даже когда вы применяете Collections.immutable()

pure4j предоставляет измененные версии постоянных коллекций Clojure (включая, например, дженерики), а также проверку неизменяемости ваших объектов, а также проверку того, что коллекции не могут измениться.

Проект Корнелиуса Мунда, https://github.com/cornim/ClojureCollections также предоставляет коллекции clojure без гарантий неизменяемости элемента, если это то, что вам нужно.