JVM上的功能性/不可变数据结构？

Question

有没有人知道一个Java/JVM数据结构库，可以提供函数式(也就是不可变的，或者在函数式意义下称为“持久化”的)等效Java数据结构？

"函数式"的含义是指对象本身是不可变的，而对这些对象的修改会返回一个新对象，该新对象在适当情况下与父对象共享相同的内部结构（无论是时间上还是空间上都更加高效；一个天真的实现可能只是在每次写操作时复制整个对象）。

就像Java的并发库一样，这似乎不是我自己能够或应该实现的东西，因此有一个我可以在JVM中使用的函数式数据结构库将是很好的。

- Pierre-Évariste

Answer 1

Clojure的不可变和持久化数据结构已被提取为Java库。您可以在http://github.com/krukow/clj-ds找到它们。这些数据结构不依赖于Clojure运行时，因此可以在应用程序类路径中不使用clojure.jar的情况下使用。它们已被泛型化以与Java代码平滑地工作。

请注意，在Java中使用这些不可变数据结构可能不太符合惯用语。

Github页面没有可供下载的jar文件。您将需要检出源代码并自行构建jar文件。

- Abhinav Sarkar

---

这正是我正在寻找的！ - Adam Arold

很好的想法，但是代码已经没有维护了5年。当然，这个回答已经有9年了。 - Jason

Answer 2

试试Functional Java。它包含不可变的映射、集合、列表和树。然而，这个库远不止是一组不可变数据结构！

- Bolo

Answer 3

在大多数Scala集合库中，函数式和不可变性是核心属性。Scala编译成JVM并与Java互操作良好。Scala语法也比Clojure（Lisp语法）更接近Java。

这是Scala集合API的介绍页面。 http://www.scala-lang.org/docu/files/collections-api/collections.html

- Bernard

---

我不建议使用Scala。它是一种复杂和华丽的语言，与其不同版本不具备二进制兼容性。 - Adam Arold

Answer 4

尝试使用Guava，它有不可变的map、list和set。此外，它还提供了一些实用工具来支持不可变集合，而不是修改基础对象，返回新的对象。

- nanda

---

番石榴是非常好的，但它的不可变数据结构并不是“函数式”的：突变操作会抛出UnsupportedOperationException，而不是以某种方式返回更新后的副本。后者需要完全不同的API。请注意，这并不是对Guava的批评；开发人员只是认为与标准Java集合的API兼容性比支持函数式习惯更重要。 - mergeconflict

Answer 5

我能理解为什么并发类很难编写：在那里很容易出现难以察觉的错误。

Java 有一种不错的方法可以避免在编写不可变的 Collection 类时出现此类错误：每种 Collection 都有一个类似于 `java.util.Collections.unmodifiableSet(someSet)` 的方法，它会给你一个包装器，让你看到底层的 Collection，但会阻止所有的改变方法。但它只是一个包装器：如果你保留了对底层 Collection 的引用，仍然可以更改它，所以不要这样做。另外，立即克隆和包装任何来自你无法控制的 Collection，因为将它们交给你的程序员可能稍后修改它们，从而改变你好的不可变数据。

---

如果你想创建一个库来处理所有这些细节上的预防措施，那需要花费时间但不难。为了节省你的时间，我已经包含了一个最小化优化的 FunctionalHashSet 示例，并进行了所有必要的变异预防。

我通过查看API列表中的Set（不要忘记toString）制作了一个抽象超类。对于非变异方法，我只需将它们传递给基础Set。对于变异方法，我会抛出UnsupportedOperationException并提供替代的函数式方法。

这是那个抽象类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<E> implements Set<E> {
  // final to prevent mutations through reassignment.
  protected final Set<E> 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<E> set)
    { this.set = Collections.unmodifiableSet(set); }

  public abstract FunctionalSet<E> clone();
  public abstract FunctionalSet<E> fAdd(final E element);
  public abstract FunctionalSet<E> fAddAll(final Collection<? extends E> elements);
  public abstract FunctionalSet<E> fRemove(final Object element);
  public abstract FunctionalSet<E> fRemoveAll(final Collection<?> elements);
  public abstract FunctionalSet<E> fRetainAll(final Collection<?> elements);

  protected abstract FunctionalSet<E> newFSet(final Set<E> newSet);
  protected abstract Set<E> newSet();
  protected abstract Set<E> cloneSet();

  protected final FunctionalSet<E> __fAdd(final E element) {
    if (set.contains(element)) return this;
    final Set<E> newSet = cloneSet();
    newSet.add(element);
    return newFSet(newSet);
  }

  protected final FunctionalSet<E> __fAddAll(final Collection<? extends E> elements) {
    if (set.containsAll(elements)) return this;
    final Set<E> newSet = cloneSet();
    newSet.addAll(elements);
    return newFSet(newSet);
  }

  protected final FunctionalSet<E> __fRemove(final Object element) {
    if (!set.contains(element)) return this;
    final Set<E> newSet = cloneSet();
    newSet.remove(element);
    return newFSet(newSet);
  }

  protected final Set<E> __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<E> newSet = cloneSet();
    newSet.removeAll(elements);
    return newFSet(newSet);
  }

  @SuppressWarnings("unchecked")
  protected final Set<E> __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<E> 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<? extends E> 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<E> iterator()
    { return set.iterator(); }
  public final int size()
    { return set.size(); }
  public final Object[] toArray()
    { return set.toArray(); }
  public final <E> 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<E> extends FunctionalSet<E> implements Cloneable {
  public static final FunctionalHashSet EMPTY = new FunctionalHashSet();

  public FunctionalHashSet()
    { super(new HashSet<E>()); }
  public FunctionalHashSet(final HashSet<E> set)
    { this(set, true); }
  @SuppressWarnings("unchecked")
  private FunctionalHashSet(final HashSet<E> set, final boolean clone)
    { super(clone ? (HashSet<E>) set.clone() : set); }
  public FunctionalHashSet(final Collection<E> elements)
    { this(new HashSet<E>(elements)); }

  protected FunctionalHashSet<E> newFSet(final Set<E> newSet)
    { return new FunctionalHashSet<E>((HashSet<E>) newSet, false); }
  protected HashSet<E> newSet()
    { return new HashSet<E>(); }
  @SuppressWarnings("unchecked")
  protected HashSet<E> cloneSet()
    { return new HashSet<E>(set); }

  public FunctionalHashSet<E> clone()
    { return this; }
  public FunctionalHashSet<E> fAdd(final E element)
    { return (FunctionalHashSet<E>) __fAdd(element); }
  public FunctionalHashSet<E> fAddAll(final Collection<? extends E> elements)
    { return (FunctionalHashSet<E>) __fAddAll(elements); }
  public FunctionalHashSet<E> fRemove(final Object element)
    { return (FunctionalHashSet<E>) __fRemove(element); }
  public FunctionalHashSet<E> fRemoveAll(final Collection<?> elements)
    { return (FunctionalHashSet<E>) __fRemoveAll(elements); }
  public FunctionalHashSet<E> fRetainAll(final Collection<?> elements)
    { return (FunctionalHashSet<E>) __fRetainAll(elements); }
}

一些注意事项：

• 在每个功能性变异方法中，我都会检查是否实际上会有任何更改。如果没有，我只返回完全相同的FunctionalSet。
• 在clone中，我只返回完全相同的FunctionalSet
• 通过运行set通过java.util.Collections.unmodifiableSet并声明它为final，可以防止两种突变来源：用户无法通过Iterator进行突变，实现者无法在其实现中意外突变。

您可以将其稍微修改一下以支持其他Collection。

- Olathe

---

这个答案涉及到不可变性，但是忽略了持久化数据结构的一个主要优点：最大化共享实例之间的公共子结构。 - mergeconflict

Answer 6

Java集合可能并不像您希望的那样不可变，即使您应用了 Collections.immutable()。

pure4j 提供了 Clojure 持久化集合的修改版本（包括泛型），还提供对象的编译时不可变性检查，从而为您提供一些保证，使集合无法更改。

Cornelius Mund 的项目 https://github.com/cornim/ClojureCollections 也提供了 Clojure 集合，但没有元素不可变性保证，如果您需要的话。

- Rob Moffat