В чем сложность оператора cons в Scala / OCaml? - PullRequest
Новая
       9

В чем сложность оператора cons в Scala / OCaml?

0 голосов
/ 15 октября 2019

Что такое сложность этих кодов?

Я написал следующий код: 

let rec replicate (element, reps) = 
    if reps < 0 then failwith "Negative reps"
    else if reps = 0 then []
    else element :: replicate (element, reps - 1);;

def replicate[A](element:A, reps:Int):List[A] = 
if (reps < 0) throw new Exception("Negative reps")
else if (reps == 0) Nil
else element :: replicate(element, reps-1)

Мне особенно интересно, какова сложность оператора cons (::).

1 Ответ

3 голосов
/ 15 октября 2019

Минусы - O(1), поэтому эти коды O(n).

Однако этот код неэффективен, потому что он не использует хвостовую рекурсию и, следовательно, не может быть оптимизирован в цикл (или, по крайней мере, с использованием удаления хвостового вызова). ).

Что-то вроде этого лучше (для Scala) 

def replicate[A](element: A, reps: Int): List[A] = {
  @annotation.tailrec
  def loop(rem: Int, res: List[A]): List[A] =
    if (rem <= 0) {
      res
    } else {
      loop(rem - 1, element :: res)
    }

  if (reps < 0) {
    throw new Exception("Negative reps")
  } else {
    loop(reps, Nil)
  }
}

Это оптимизировано для цикла в Scala, а также позволяет избежать проверки состояния ошибки на каждой итерации.

Конечно, в Scala проще использовать 

List.fill(reps)(element)
...