この記事では、
を使用して Java で LinkedList の永続的かつ不変のバリエーションを実装します。
部分的な構造共有により時間と空間の効率が向上します。
リンク リストは、各ノードに値とシーケンス内の次のノードへの参照が含まれるノードのコレクションで構成されるデータ構造です。リストの先頭に要素を追加したり、先頭から要素を削除したりするような操作は O(1) 操作です。ただし、リストの末尾に要素を追加したり、末尾から要素を削除したりするような操作は、O(n) 回の操作です (n はリスト内の要素の数です)。
関数型プログラミングでは、不変性が重要な概念です。不変性とは、データ構造が一度作成されると、
変更することはできません。代わりに、変更を加えて新しいデータ構造が作成され、元のデータ構造は変更されません。
このプロパティにより、次のような利点が得られます。
ただし、Java のコレクションは、この記事の焦点が LinkedList にあるため、デフォルトで変更可能です。理由はたくさんあるかもしれません
コレクションが設計されたときの思い付きではないことから、
に固有のパフォーマンス上の理由に至るまで、
不変のデータ構造。
JDK は、元のコレクションのラッパーである変更不可能なコレクションを提供します。これらは不変性をサポートしますが、永続的ではなく、真の型で安全な方法を提供しません。これらは元のコレクションのラッパーであり、
変更操作が呼び出されたときに例外をスローします。これは、実行時に UnsupportedOperationException が発生しにくくなる一方で、データ構造をまったく変更できない不変性とは異なります。
永続的と不変という用語はしばしば同じ意味で使用されますが、意味は異なります。不変性ではデータ構造の変更は許可されませんが、永続性ではデータ構造が変更された場合にその構造を共有できます。これは、データ構造が変更されるとき、つまり新しいバージョンが作成されるときに、古いデータ構造の一部を新しいデータ構造と共有でき、時間とスペースの効率が向上することを意味します。この手法は構造共有と呼ばれます。
データ構造の永続性を実現するには複数の方法があります。データ構造は、単純なものから、AVL や赤黒ツリーなどのバランス ツリーの使用などの複雑なもの、フィンガー ツリーや基数ベースのバランス ツリーなどのより複雑なものまで多岐にわたります。
この記事では、部分的な構造共有を備えた永続的かつ不変の LinkedList のより単純なバージョンを実装します。その理由は、LinkedList は単純なデータ構造であり、不変性と永続性の概念をより深く理解するのに役立ちますが、通常、より複雑なデータ構造の実装は本質的に困難な作業であるためです。
以下では、段階的なアプローチを使用して、Java で永続的かつ不変の単独の LinkedList を実装します。
Java への関数型プログラミングのツアーを支援する完全な実装と追加のモナドとユーティリティについては、この素晴らしい小さなライブラリ FunctionalUtils をチェックしてください。
LinkedList に付ける名前は SeqList となり、汎用クラスになります。
最初に、リストでサポートする操作について考える必要があります。
LinkedList は、各ノードが以下を含むノードで構成される構造として考えることができます。
完全な実装はここにあります
リストの最後の要素が空の LinkedList で、各要素が先頭と末尾を持つノードであるとすると、LinkedList を 2 つのクラスで構成される再帰データ構造として表すことができます。
public record Empty<T>() implements SeqList<T> {
}
public record Cons<T>(T head, SeqList<T> tail) implements SeqList<T> {
}
ここで、Cons は、Construct という名前の関数型プログラミング用語であり、その起源は Lisp プログラミング言語にまで遡ります。
上記を考慮すると、SeqList インターフェースを次のように実装できます:
public sealed interface SeqList<T> permits Empty, Cons {
/**
* Creates an empty list.
*
* @param <T> the type of the elements
* @return an empty list
*/
static <T> SeqList<T> empty() {
return new Empty<>();
}
/**
* Creates a new list with the given elements. The complexity of this method is O(n) where n is
* the number of elements.
*
* @param elements the elements to add
* @param <T> the type of the elements
* @return a new list with the elements added
*/
@SafeVarargs
static <T> SeqList<T> of(T... elements) {
SeqList<T> list = empty();
for (int i = elements.length - 1; i >= 0; i--) {
list = list.add(elements[i]);
}
return list;
}
/**
* Prepends the element to the list. The complexity of this method is O(1).
*
* @param element the element to add
* @return a new list with the element prepended
*/
default SeqList<T> add(T element) {
return new Cons<>(element, this);
}
}
上で書いたことを詳しく見てみましょう:
残りの操作を実装する必要があります。削除操作から始めましょう:
/**
* Removes the first occurrence of the element from the list. If the element is not found, the
* list is returned as is. The complexity of this method is O(n) where n is the number of
* elements. It uses structural sharing up to the element to remove. If the element is not found
* the structural sharing is not utilized.
*
* @param element the element to remove
* @return a new list with the element removed
* @throws StackOverflowError for infinite lists
*/
default SeqList<T> remove(T element) {
if (isEmpty()) {
return this;
}
if (head().equals(element)) {
return tail();
}
return new Cons<>(head(), tail().remove(element));
}
さらに、tail() メソッドとその他の便利なメソッドをサブクラスに実装します。
public record Cons<T>(T head, SeqList<T> tail) implements SeqList<T> {
@Override
public boolean isEmpty() {
return false;
}
@Override
public Optional<T> headOption() {
return Optional.ofNullable(head);
}
@Override
public Optional<T> last() {
if (tail.isEmpty()) {
return Optional.ofNullable(head);
}
return tail.last();
}
}
public record Empty<T>() implements SeqList<T> {
@Override
public boolean isEmpty() {
return true;
}
@Override
public T head() {
throw new UnsupportedOperationException("head() called on empty list");
}
@Override
public Optional<T> headOption() {
return Optional.empty();
}
@Override
public SeqList<T> tail() {
throw new UnsupportedOperationException("tail() called on empty list");
}
@Override
public Optional<T> last() {
return Optional.empty();
}
}
remove メソッドの実装からわかるように、再帰呼び出しを使用して要素を削除しています
リスト。これは関数型プログラミングの典型的なパターンで、再帰を使用してリストを走査し、
要素を削除します。無限リストの場合はスタック オーバーフローを避けるように注意する必要があります。将来の改善としては、Java ではサポートされていない末尾再帰最適化を使用することが考えられますが、トランポリンを使用すると実現できる可能性があります。
最後に、map 操作と flatMap 操作を実装してリストをモナドに変換しましょう:
/**
* Applies a map function to the elements of the list. The complexity of this method is O(n) where
* n is the number of elements.
* <b>It does not use structural sharing</b> as it requires advanced data structures to achieve
* it.
*
* @param fn the map function
* @param <U> the type of the elements of the new list
* @return a new list with the elements mapped
* @throws StackOverflowError for infinite lists
*/
default <U> SeqList<U> map(Function<? super T, ? extends U> fn) {
if (isEmpty()) {
return empty();
}
return new Cons<>(fn.apply(head()), tail().map(fn));
}
/**
* Applies a flat map function to the elements of the list. The complexity of this method is O(n)
* where n is the number of elements.
* <b>It does not use structural sharing</b> as it requires advanced data structures to achieve
* it.
*
* @param fn the flat map function
* @param <U> the type of the elements of the new list
* @return a new list with the elements flat mapped
* @throws StackOverflowError for infinite lists
*/
default <U> SeqList<U> flatMap(Function<? super T, ? extends SeqList<U>> fn) {
if (isEmpty()) {
return empty();
}
SeqList<U> mappedHead = fn.apply(head());
SeqList<U> newTail = tail().flatMap(fn);
return concat(mappedHead, newTail);
}
/**
* Concatenates two lists. The complexity of this method is O(n) where n is the number of
* elements.
*
* @param list1 the first list
* @param list2 the second list
* @param <T> the type of the elements
* @return a new list with the elements of the two lists concatenated
* @throws StackOverflowError for infinite lists
*/
static <T> SeqList<T> concat(SeqList<T> list1, SeqList<T> list2) {
if (list1.isEmpty()) {
return list2;
}
return new Cons<>(list1.head(), concat(list1.tail(), list2));
}
map メソッドと flatMap メソッドの実装からわかるように、再帰呼び出しを使用してリストを走査し、各要素に関数を適用しています。 flatMap メソッドは、リストの残りの部分と連結する必要がある新しいリストを返す関数を必要とするため、少し複雑です。どちらの方法でも、構造共有の難しさは有名であり、高度なデータ構造を使用することが重要であるため、構造共有は使用していません。今後の改善点については今後の記事で検討していきます。
SeqList の使用例をいくつか見てみましょう。
SeqList<Integer> list = SeqList.of(1, 2, 3, 4, 5, 6); SeqList<Double> updatedList = list .filterOut(number -> number % 2 == 0) .map(number -> Math.pow(number, 2));
SeqList<String> list = SeqList.of("a", "b", "c", "d", "e");
SeqList<String> updatedList = list
.map(letter -> "prefix" + letter + "suffix");
SeqList<SeqList<Integer>> list = SeqList.of(SeqList.of(1, 2), SeqList.of(3, 4), SeqList.of(5, 6)); SeqList<Integer> updatedList = list .flatMap(seqList -> seqList);
SeqList<Integer> list = SeqList.of(1, 2, 3, 4, 5, 6);
switch (list) {
case Empty() -> {
// do something
}
case Cons<Integer> cons -> {
//do something else
}
}
この記事では、部分的な構造共有を備えた永続的で不変の LinkedList を Java に実装しました。不変性と永続性の利点と、Java でそれらを実現する方法を示しました。また、関数の合成を容易にするために、LinkedList をモナドに変換する方法も示しました。永続的および不変のデータ構造の長所と短所、およびそれらを実際に使用する方法について説明しました。
以上が永続的かつ不変の Java LinkedListの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。
![[Web フロントエンド] Node.js クイック スタート](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
