この記事では、Java で LinkedList の永続的かつ不変のバリエーションを実装します
部分的な構造共有により、時間と空間の効率が向上します
リンク リストは、各ノードに値とシーケンス内の次のノードへの参照が含まれるノードのコレクションで構成されるデータ構造です。リストの先頭に要素を追加したり、先頭から要素を削除したりするような操作は O(1) 操作です。ただし、リストの末尾に要素を追加したり、末尾から要素を削除したりするような操作は O(n) 操作です。ここで、n はリスト内の要素の数です。
関数型プログラミングでは、不変性が重要な概念です。不変性とは、データ構造が一度作成されると、
変更することはできません。代わりに、変更を加えて新しいデータ構造が作成され、元のデータ構造は変更されません。
不変のデータ構造
変更不可能な JDK コレクションとこの LinkedList の違い
永続的 vs 不変的
と呼ばれます。 データ構造の永続性を実現するには複数の方法があります。データ構造は、AVL や赤黒ツリーなどのバランス ツリーを使用する単純なものから複雑なもの、フィンガー ツリーや基数ベースのバランス ツリーなどのより複雑なものまで多岐にわたります。
この記事では、部分的な構造共有を備えた永続的かつ不変の LinkedList のより単純なバージョンを実装します。その理由は、LinkedList は単純なデータ構造であり、不変性と永続性の概念をより深く理解するのに役立ち、通常、より複雑なデータ構造の実装は本質的に困難な作業であるためです。実装
以下では、段階的なアプローチを使用して、Java で永続的かつ不変の単独の LinkedList を実装します。
LinkedList に付ける名前は SeqList となり、汎用クラスになります。
最初に、リストでサポートする操作について考える必要があります。
O(1) 操作となるリストの先頭に追加します。
リストからの要素の削除。要素が末尾の方にある場合、最悪でも O(n) 操作になります。
The full implementation can be found in here
Given that the last element of the list is an empty LinkedList and each element is a node with a head and a tail, we can represent our LinkedList as a recursive data structure consisting of two classes:
public record Empty() implements SeqList { } public record Cons (T head, SeqList tail) implements SeqList { }
where Cons is a functional programming term named Construct dates back to the Lisp programming language.
Given the above, we can implement the SeqList interface as follows:
public sealed interface SeqListpermits Empty, Cons { /** * Creates an empty list. * * @param the type of the elements * @return an empty list */ static SeqList 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 the type of the elements * @return a new list with the elements added */ @SafeVarargs static SeqList of(T... elements) { SeqList 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 add(T element) { return new Cons<>(element, this); } }
Let's break down what we wrote above:
We need to implement the remaining of our operations. Let's start with the remove operation:
/** * 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 SeqListremove(T element) { if (isEmpty()) { return this; } if (head().equals(element)) { return tail(); } return new Cons<>(head(), tail().remove(element)); }
And additionally implement the tail() method and some other useful ones in our subclasses:
public record Cons(T head, SeqList tail) implements SeqList { @Override public boolean isEmpty() { return false; } @Override public Optional headOption() { return Optional.ofNullable(head); } @Override public Optional last() { if (tail.isEmpty()) { return Optional.ofNullable(head); } return tail.last(); } } public record Empty () implements SeqList { @Override public boolean isEmpty() { return true; } @Override public T head() { throw new UnsupportedOperationException("head() called on empty list"); } @Override public Optional headOption() { return Optional.empty(); } @Override public SeqList tail() { throw new UnsupportedOperationException("tail() called on empty list"); } @Override public Optional last() { return Optional.empty(); } }
As we can examine from the implementation of the remove method we are using recursive calls to remove the element from
the list. This is a typical pattern in functional programming where we are using recursion to traverse the list and
remove the element. Care should be taken to avoid stack overflows in case of infinite lists. A future improvement could be to use tail recursion optimization which is not supported in Java but could be achieved using trampolining.
Lastly, let's implement the map and flatMap operations to turn our List into a Monad:
/**
* 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.
* It does not use structural sharing as it requires advanced data structures to achieve
* it.
*
* @param fn the map function
* @param the type of the elements of the new list
* @return a new list with the elements mapped
* @throws StackOverflowError for infinite lists
*/
default SeqList map(Function 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.
* It does not use structural sharing as it requires advanced data structures to achieve
* it.
*
* @param fn the flat map function
* @param the type of the elements of the new list
* @return a new list with the elements flat mapped
* @throws StackOverflowError for infinite lists
*/
default SeqList flatMap(Function> fn) {
if (isEmpty()) {
return empty();
}
SeqList mappedHead = fn.apply(head());
SeqList 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 the type of the elements
* @return a new list with the elements of the two lists concatenated
* @throws StackOverflowError for infinite lists
*/
static SeqList concat(SeqList list1, SeqList list2) {
if (list1.isEmpty()) {
return list2;
}
return new Cons<>(list1.head(), concat(list1.tail(), list2));
}
As we can see from the implementation of the map and flatMap methods we are using recursive calls to traverse the list and apply the function to each element. The flatMap method is a bit more complex as it requires the function to return a new list which we need to concatenate with the rest of the list. Both methods are not using structural sharing due to its notoriety difficulty and the importance of using advanced data structures. A future improvement will be examined in a future article.
Let's see some usage examples of our SeqList.
SeqListlist = SeqList.of(1, 2, 3, 4, 5, 6); SeqList updatedList = list .filterOut(number -> number % 2 == 0) .map(number -> Math.pow(number, 2));
SeqListlist = SeqList.of("a", "b", "c", "d", "e"); SeqList updatedList = list .map(letter -> "prefix" + letter + "suffix");
![[Web フロントエンド] Node.js クイック スタート](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
