Ocaml：函数计算两个整数并返回范围内所有整数的列表

Question

该函数接受两个整数并返回 [a,b] 范围内所有整数的列表，

这是我编写的解决方案。

let rec range_rec l a b = 
  if (a=b) then l@[b]
  else range_rec (l@[a], a+1, b);;

let range a b = range_rec [] a b;;

我遇到错误“错误：此表达式的类型为 int list * int * int，但表达式应为 int 类型”。有人可以解释一下为什么我会收到此错误吗？

谢谢。

Answer 1

它应该看起来像这样：

let rec range_rec l a b = 
  if a = b then l @ [b]
  else range_rec (l @ [a]) (a + 1) b;;

let range a b = range_rec [] a b;;

我所做的：

1. 将 loop 更改为 range_rec
2. 更改 (l@[a], a+1, b) 到 (l @ [a]) (a + 1) b。第一个是三元组，第二个是柯里化函数的 3 个参数。
3. 请注意，if (a = b) then 可以写为 if a = b then。

最后，通过“向后”循环使用 :: 而不是 @ 可以使该函数更加高效。例如，像加斯切（gasche）所展示的那样。

Answer 2

从性能角度来看，l @ [elem] 操作非常糟糕：因为 a @ b 与 a 的长度呈线性关系，因此添加一个元素到列表末尾与列表长度呈线性关系，使整个 range_rec 定义在 |ba| 中呈二次方关系。解决方法是更改​​代码，以便可以使用恒定时间 elem::l 操作。

let rec range a b =
  if a > b then []
  else a :: range (a + 1) b

您可以进行其他优化，例如使其成为尾递归，但至少该解决方案的复杂性是正确的。

Answer 3

为了改进gasche已经建议的解决方案，可以将其设为尾递归。

let int_range a b =
  let rec int_range_rec l a b =
    if a > b then l
    else int_range_rec (b :: l) a (b - 1)
  in (int_range_rec [] a b);;