递归 case-class: java.lang.StackOverflowError on equals

Question

我正在玩Scala函数式编程的练习，实现了一个简单的单链表。

相关实现部分如下：

sealed trait List[+T]

case class Cons[+T](t: T, ts: List[T]) extends List[T]
case object Empty extends List[Nothing]

我构建了一个"very big"列表（隐藏的目标是实现尾递归foldRight）：

def mkBigListOfInt(start: Int, end: Int) = (start to end).foldRight(workshop.List[Int]()) {
  case (item, acc) => Cons(item, acc)
}

val veryBigList = mkBigListOfInt(1, 1000000)

当我尝试将列表与另一个列表进行比较（例如，使用 Scalatest DSL）时出现问题：

mkBigListOfInt(1, 1000000) shouldBe mkBigListOfInt(1, 1000000)

我得到：

[error] java.lang.WhosebugError
[error]     at scala.runtime.BoxesRunTime.equals(BoxesRunTime.java:123)
[error]     at workshop.Cons.equals(list.scala:81)
[error]     at workshop.Cons.equals(list.scala:81)
...

（第 81 行是我定义 Cons 案例 class 的行）

实施 Cons 以允许比较相等的好方法是什么？

因为这是一个练习，我可以保持简单和不完整（前提是发现权衡），所以 "basic" 解决方案现在就可以了。

Answer 1

case class equals 的默认实现是天真的递归。您可以在 List 中实现自己的尾递归版本。这是一个开始：

sealed trait List[+T] {
  override def equals(o: Object): boolean = o match {
    case ls: List[_] => equalsRec(ls)
    case _ => false
  }

  @tailrec
  def equalsRec(ls: List[_]): boolean = ???

递归 case-class: java.lang.StackOverflowError on equals

Recursive case-class: java.lang.StackOverflowError on equals

scala

tail-recursion