在阅读这篇文章前，请务必阅读这三篇文章
定义列表
在函数式编程里，列表是递归定义的，即：
列表的第一个元素，称为head;
列表的剩余部分还是一个列表，称为tail;
正如你处理递归调用需要一个终止条件，列表也是如此，我们称这个终止情况为Nil,或者叫它空列表，它没有head和tail。因此，我们需要两种类来表示链表，一个表示非空链表(我们使用Cons来表示。借鉴了 Lisp家族中的cons操作)，另一个表示空链表（Nil）。
例如，这有个链表，存储abcdef
基本实现如下：
public abstract class List<T> {
public abstract T head();
public abstract List<T> tail();
public abstract boolean isEmpty();
private List() {
}
java函数为基础
private static class Nil<T> extends List<T> {
private Nil() {
}
@Override
public T head() {
throw new IllegalStateException("this is empty");
}
@Override
public List<T> tail() {
throw new IllegalStateException("this is empty");
}
@Override
public boolean isEmpty() {
return true;
}
}
private static class Cons<T> extends List<T> {
private final T head;
private final List<T> tail;
private Cons(T head, List<T> tail) {
this.head = head;
this.tail = tail;
}
@Override
public T head() {
return head;
}
@Override
public List<T> tail() {
return tail;
}
@Override
public boolean isEmpty() {
return false;
}
}
}
类型参数T表示列表持有的元素类型，List类里有三个主要的抽象方法，head()用来返回列表的第一个元素，tail()返回列表的剩余元素，isEmpty()来判断列表是否为空。将类设为私有，这样你必须通过静态工厂方法才可以创建列表。
@SuppressWarnings("rawtypes")
private static final List NIL = new Nil<>();
@SuppressWarnings("unchecked")
public static <T> List<T> list() {
return NIL;
}
@SafeVarargs
public static <T> List<T> list(T... t) {
List<T> newList = list();
for (int i = t.length - 1; i >= 0; i--) {
newList = new Cons<T>(t[i], newList);
}
return newList;
}
我们在这里向list类添加了一个新属性，它没有类型参数，是一个原生类型。换句话说，它可以表示元素类型为任意的空列表，这样我们就不需要为每一个参数类型创建一个不同的空列表了。上面两个静态方法是通用的，所以放在List类里。
操作列表：
1：向大家展示列表—toString方法：
String返回一个列表的字符串描述，
这个方法每个类要分别实现：
在Nil类里实现非常简单：
@Override
public String toString() {
return "[NIL]";
}
而在Cons类里，我们使用StringBuilder作为一个累加器。
我们先看第一个版本的实现：
@Override
public String toString() {
return toString(new StringBuilder(), this);
}
private String toString(StringBuilder acc,List<T> list) {
return list.isEmpty()
?acc.append("Nil").toString()
:toString(acc.append(list.head()).append(", "), list.tail());
}
这是一个递归的方法，操作也符合列表的定义，但是当列表很大时，可能会发生爆栈的现象，我们现在按照前面讲的把它改成栈安全的：
@Override
public String toString() {
return String.format("[%sNil]", toString(new StringBuilder(), this) .eval());
}
private TailCall<StringBuilder> toString(StringBuilder acc,List<T> list) {
return list.isEmpty()
?ret(acc)
:sus(()->toString(acc.append(list.head()).append(", "),list.tail()));
}
2在头部添加元素—cons方法。
要知道，一个Nil添加一个元素后就是Cons了，所以这个方法在两个子类中实现相同，可以放在List类里面：
public Cons<T> cons(T head){
return new Cons<>(head, this);
}
3.替换操作—设置头部新制—setHead方法
public abstract List<T> setHead(T newHead);
Nil类实现很简单
@Override
public List<T> setHead(T newHead) {
throw new IllegalStateException("this is empty");
}
Cons类实现如下：
@Override
public List<T> setHead(T newHead) {
return new Cons<T>(newHead, tail());
}
4.删除前n个元素—drop方法
列表里tail方法产生的效果与删除第一个元素的效果一样，我们可以使用它来帮我们完成drop方法。
public abstract List<T> drop(int n);
Nil类实现很简单
@Override
public List<T> drop(int n) {
return this;
}
Cons类实现如下：
@Override
public List<T> drop(int n) {
return n <= 0 ? this : drop0(this, n).eval();
}
private TailCall<List<T>> drop0(List<T> list, int n) {
return n <= 0 || list.isEmpty() ? ret(this) : sus(() -> drop0(list.tail(), n - 1));
}
这个方法有一个变种，dropWhile(Function<T,Boolean> p),只要条件为真，就不断的删除，只要遇到一个不满足条件的元素就终止。在Cons类里，它是这样实现的：
@Override
public List<T> dropWhile(Function<T, Boolean> p) {
return dropWhile0(this, p).eval();
}
private TailCall<List<T>> dropWhile0(List<T> list, Function<T, Boolean> p) {
return list.isEmpty() || p.apply(list.head()).equals(Boolean.FALSE) ? ret(list)
: sus(() -> dropWhile0(list.tail(), p));
}
5.反转列表—reverse方法
我们的链表只能从头部开始操作，当遇到删除最后一个非空元素，或者做链表的链接时，这很不方便，因此我们需要一个能将链表反转的方法。（NIL反转后还是NIL，这里不做介绍，它返回this）
要知道，我们创建新链表（cons操作），它只能向前添加，我们可以利用它来反转链表。
原理如下：
这是一个带反转的链表
反转操作前我们都需要一个Nil，实际上它是同一个，由list()方法返回。
@Override
public List<T> reverse() {
return reverse0(list(), this).eval();
}
private TailCall<List<T>> reverse0(List<T> acc, List<T> list) {
return list.isEmpty() ? ret(acc) : sus(() -> reverse0(new Cons<>(list.head(), acc), list.tail()));
}
6.删除末尾元素—dropLast
Nil类抛出异常，我们主要看Cons类如何操作（使用上一个反转方法实现）：
@Override
public List<T> dropLast() {
return reverse().tail().reverse();
}
7.连接操作-concat方法
如图，这有两个要进行连接的链表，你要注意连接后还要保持原有的元素顺序。
结果可能是这样：
也可能是这样。
我们只能操作头元素，所以你可以将某个链表反转后执行连接。这个方法对两个子类都使用，所以放在List类里。
public static <T> List<T> concatByreverse(List<T> list1, List<T> list2) {
List<T> newList1 = list1.reverse();
while (!newList1.isEmpty()) {
list2 = new Cons<T>(newList1.head(), list2);
}
return list2;
}
又或者我们不做反转：
public static <T> List<T> concat(List<T> list1, List<T> list2) {
return list1.isEmpty() ? list2 : new Cons<T>(list1.head(), concat(list1.tail(), list2));
}
如果List1太长，可能会导致爆栈，你也可以尝试使用我们前面讲过的TailCall优化。
这里连接操作的时间复杂度只与第一个链表有关，所以实际操作中要考虑好将谁作为第一个链表。你可以看出我并没有给出栈安全的方法实现，因为在下一章中，你将看到更简单的实现方式。
8.遍历操作—foreach方法
这是一个对两个类都适用的方法，故放在List类里
public void forEach(Consumer<T> f) {
List<T> workList = this;
while (!workList.isEmpty()) {
f.accept(workList.head());
workList = workList.tail();
}
}
9.转换为Java里的列表形式—toJavaList方法
这个操作很简单
public java.util.List<T> toJavaList() {
java.util.List<T> newList = new ArrayList<>();
List<T> workList = this;
while (!workList.isEmpty()) {
newList.add(workList.head());
workList = workList.tail();
}
return newList;
}
下一章我将介绍如何使用高阶函数操作列表。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/10154.html