如何在Scala中实现链表时使用Cons

Question

我一直在尝试在scala中为大学课程实现linkedList。到目前为止，我已经实现了Empty和ConstructorCons以及其他一些方法。现在我试图实现过滤器功能，由于我没有进展，我看了一下教授给我们的解决方案。这就是他在LinkedList:上实现过滤的方法

override def filter(filterFunc: Int => Boolean): IntList = this match {
case Empty => Empty
case Cons(head, tail) if filterFunc(head) => Cons(head, tail.filter(filterFunc))
case Cons(_, tail) => tail.filter(filterFunc)
}

我的问题是case Cons(_, tail) => tail.filter(filterFunc)到底做什么？我知道filter函数是在尾部递归应用的，但我不明白它是如何附加到应该在末尾返回的列表中的。我希望我的问题有道理，提前谢谢！

Answer 1

您应该理解的第一件事-Cons(head, tail)-它只是新List的构造函数。第二件事-建设：

this match {
case Empty => Empty
case Cons(head, tail) if filterFunc(head) => Cons(head, tail.filter(filterFunc))
case Cons(_, tail) => tail.filter(filterFunc)
}

从上到下，并尝试将当前列表与模式匹配：Empty、Cons(head, tail) if filterFunc(head)或case Cons(_, tail)。若列表不为空，并且head传递谓词filterFunc，它会构造具有相同head的新列表，并在尾部调用filter函数，若您这样做，您将从每个调用filter函数中获得新列表。在case Cons(_, tail) => tail.filter(filterFunc)行中，它没有将过滤函数的结果附加在尾部，它只是返回没有这个头并且带有过滤尾部的新列表。如果它是来自另一个地方的递归调用，那么在这个调用中，新列表将被构造为一个新对象，其头部和调用结果作为尾部。请尝试阅读有关递归数据结构的更多信息。