Хвостовая рекурсия

Question

Мы экспериментировали с параллельными коллекциями в Scala и хотели проверить, был ли заказан результат. Для этого я написал небольшую функцию в REPL, чтобы выполнить эту проверку в очень большом Списке, который мы создавали:

def isOrdered(l:List[Int]):Boolean = { l match { 
  case Nil => true
  case x::Nil => true
  case x::y::Nil => x>y
  case x::y::tail => x>y & isOrdered(tail) 
  }
}

Это терпит неудачу с stackOverflow (насколько уместно для вопроса здесь!). Я ожидал, что это будет оптимизировано для хвоста. В чем дело?

Answer 1

isOrdered - это не последний вызов в вашем коде, оператор & Попробуйте это вместо этого:

@scala.annotation.tailrec def isOrdered(l:List[Int]):Boolean = { l match { 
  case Nil => true
  case x::Nil => true
  case x::y::Nil => x>y
  case x::y::tail => if (x>y) isOrdered(tail) else false
  }
}

Answer 2

Ваш алгоритм неверен. Даже с улучшением @ Ким, isOrdered(List(4,3,5,4)) возвращается true,

Попробуй это:

def isOrdered(l:List[Int]): Boolean = l match {
  case Nil => true
  case x :: Nil => true
  case x :: y :: t => if (x <= y) isOrdered(l.tail) else false
}

(также обновлено, чтобы знаки были правильными)

изменить: мой предпочтительный макет будет такой:

def isOrdered(list: List[Int]): Boolean = list match {
  case Nil      => true
  case x :: Nil => true
  case x :: xs  => if (x > xs.head) false
                   else isOrdered(xs)
}

Быстрый способ, если производительность не проблема, был бы

def isOrdered(l: List[Int]) = l == l.sorted

Answer 3

Он не может быть оптимизирован хвостом, потому что вы возвращаете это: 'x>y & isOrdered(tail)'. Это означает, что нужно будет держать его в стеке.

Используйте аннотацию @tailrec, чтобы вызвать ошибку, когда вы ожидаете, что функции будут хвостово-рекурсивными. Это также объяснит, почему этого не может быть.

Answer 4

Я думаю, что проблема в том, что вы используете битовый оператор-и (&) в вашем последнем случае. Поскольку среда выполнения должна знать значение вызова isOrdered, прежде чем она сможет оценить &, она не может оптимизировать функцию хвостом. (То есть, после вызова isOrdered необходимо выполнить больше кода - побитовую операцию и операцию.)

Использование && или оператор if может помочь.