Рекурсивный case-класс: java.lang.StackOverflowError на равных - PullRequest
Новая
       9

Рекурсивный case-класс: java.lang.StackOverflowError на равных

0 голосов
/ 16 января 2019

Я играю с упражнениями Функциональное программирование в Scala и реализовал простой односвязный список.

Вот соответствующая часть реализации: 

sealed trait List[+T]

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

Я создал «очень большой» список (скрытая цель - реализовать хвостовую рекурсию 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.StackOverflowError
[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 - строка, в которой я определил * case-класс Cons)

Что было бы хорошим способом реализовать Cons, чтобы позволить сравнение равенства?

Поскольку это упражнение, для меня нормально держать его простым и неполным (при условии, что найдены компромиссы), поэтому «базовое» решение пока подойдет.

1 Ответ

0 голосов
/ 16 января 2019

Реализация по умолчанию класса case 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 = ???
...