Scala/OCaml 中缺点运算符的复杂性是多少?

Question

这些代码的复杂性是多少？

我编写了以下代码：

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)

我特别想知道缺点运算符 (：:) 的复杂性是什么。

Answer 1

缺点是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)

Answer 2

来自未来的回答：从 OCaml 4.14(以及更高版本，2022 年发布(开始，有tail_mod_cons这使得在保持 O(n( 的同时使用尾递归实现这一点变得微不足道。

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

尽管 OCaml 通常使用咖喱而不是传递元组。

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

而这实际上只是List.init的专业化.

let replicate element reps =
try
List.init reps @@ Fun.const element
with
| Invalid_argument _ -> failwith "Negative reps"