Java List 接口的 Cons 实例的深拷贝

Question

我正在java中实现一个不可变的List接口，一个Cons类，本质上是一个列表的列表，即；缺点(1,2,3)=缺点(1,缺点(2,缺点(3,空)))

我正在尝试创建一个缺点的深层副本，但没有成功

下面是类的构造方法和初始化：

public final class Cons<T> implements List<T> {

  private final T head;
  private List<T> tail; // non-final because of take and join

  Cons(T head, List<T> tail) {
    this.head = head;
    this.tail = tail;
  }

以下是当前的 Copy 类：

    public Cons<T> copy(Cons<T> tocopy) {
      Cons<T> test=  new Cons<T>(this.head,this.tail);
      return test;
    }
}

下面是它的调用方式，我通过附加一个值并将副本与此进行比较来确认这是简单的浅复制或引用：

public List<T> join(List<T> other) {

      Cons<T> cp= copy(this);
      if(other instanceof Nil){
          return cp;
      }
      Cons<T> ptr= (Cons<T>) other;

      for(; ptr instanceof Cons;ptr= (Cons<T>) ptr.tail){
          if(!(ptr.tail instanceof Cons)){
              cp.append(ptr.head);
              break;
          }
          else{
              cp.append(ptr.head);
          }
      }
      return cp;
  }

另外我尝试过 Cons copy = cons(this.head, this.tail),

Answer 1

当你说你正在制作一个

不可变

缺点列表时，我不确定为什么你将tail定为非最终版本。另外，

tail

是

List

类型（

java.util.List

？），而它应该是

Cons

或

Nil

类型。

让我们通过使用密封接口

ConsList<T>

来解决这些问题，

Cons<T>

和

Nil<T>

实现该接口。我们还制作

Cons<T>

和

Nil<T>

记录，以便它们是不可变的。

sealed interface ConsList<T> permits Cons, Nil {}
record Cons<T>(T head, ConsList<T> tail) implements ConsList<T> { }
record Nil<T>() implements ConsList<T> {}

现在

copy

可以这样实现：

static <T> ConsList<T> copy(ConsList<T> list) {
    Deque<T> stack = new ArrayDeque<>();
    ConsList<T> temp = list;
    while (temp instanceof Cons<T> cons) {
        stack.push(cons.head());
        temp = cons.tail();
    }
    temp = new Nil<>();
    while (!stack.isEmpty()) {
        temp = new Cons<>(stack.pop(), temp);
    }
    return temp;
}

这也可以通过递归来完成，但与 Haskell 这样的函数式语言不同，Java 对于这样的递归代码没有太多优化，所以我不建议这样做。对于稍大的列表，堆栈可能会溢出。

您会意识到，您实际上并不需要这样的

copy

方法。在您的

join

方法中，进行深层复制的唯一原因是您稍后调用

cp.append

。虽然你没有展示实现，但我只能假设它以某种方式发生了变化。这不是

不可变

数据类型应该做的事情。 相反，您应该通过将每个列表的元素收集到堆栈中，然后通过从堆栈中弹出来创建连接列表来实现

cp

。

join

你也可以用递归来写这个，这会让代码看起来“更好”，但同样，我不建议这样做。也就是说，重复的代码可以稍微重构一下：

// in ConsList<T> interface
default ConsList<T> join(ConsList<T> other) {
    Deque<T> stack = new ArrayDeque<>();

    // push "this"
    ConsList<T> temp = this;
    while (temp instanceof Cons<T> cons) {
        stack.push(cons.head());
        temp = cons.tail();
    }

    // push other
    temp = other;
    while (temp instanceof Cons<T> cons) {
        stack.push(cons.head());
        temp = cons.tail();
    }

    // pop everything from the stack and make a new ConsList<T>
    temp = new Nil<>();
    while (!stack.isEmpty()) {
        temp = new Cons<>(stack.pop(), temp);
    }
    return temp;
}