在 ocaml 中构建整数列表

Question

我想编写一个函数，在两个整数之间构建一个列表，包括两个整数

rec myFunc x y 将构建一个包含 x 和 y 之间所有整数的列表，包括 x 和 y

对于现在的逻辑，我有这样的东西：

let rec buildList i n = let x = i+1 in if i <= n then i::(buildList x n)

但这给了我一个错误“表达式的类型为“列表”，但预期表达式的类型为“单元”。

我认为 buildList 返回一个整数列表，而 i 作为一个整数，所以 cons 运算符是有效的，但它说它应该是 void？

为什么会发生这种情况，如何解决？

Answer 1

如果条件为真，则返回列表

i::(buildList x n)

。如果不正确，您会返回什么？

将

else []

添加到函数中，以便在不满足条件时返回空列表。 当您没有任何

else

时，编译器会认为它是

else ()

（因此出现错误消息）。

Answer 2

您的

if

缺少

else

条件

我建议你使用尾递归函数：

let buildList x y =
  let (x,y) = if x<y then (x,y) else (y,x) in
  let rec aux cpt acc =
      if cpt < x then acc
      else aux (cpt-1) (cpt::acc)
  in aux y []

首先，确保您正确排序了边界（防白痴），然后借助需要累加器的本地递归函数构建列表。

Answer 3

两种依赖于电池封装的替代方案，

使用unfold，其目的是建立列表，

let range ~from:f ~until:u = 
    BatList.unfold f (function | n when n <= u -> Some (n, succ n) | _ -> None)

使用枚举，允许使用惰性数据结构，

# BatList.of_enum @@ BatEnum.(1--9);;
- : int list = [1; 2; 3; 4; 5; 6; 7; 8; 9]

Answer 4

let buildList i n =
 let rec aux acc i =
   if i <= n then
     aux (i::acc) (i+1)
   else (List.rev acc)
 in
 aux [] i

测试：

# buildList 1 3;;
- : int list = [1; 2; 3]
# buildList 2 1;;
- : int list = []
# buildList 0 250000;;
- : int list =
[0; 1; 2; 3; .... 296; 297; 298; ...]

Answer 5

我的建议，这尊重参数的顺序。

let rec iota n m = 
  let oper = if n < m then succ else pred in 
  if n = m then [n] else n :: iota (oper n) m

编辑：

运算符选择在递归部分内部，最好在外部，如下所示：

let iota n m = 
  let oper = if n < m then succ else pred  in 
  let rec f1 n m = if n = m then [n] else n :: f1 (oper n) m in
  f1 n m

当元素超过 200000 个时，我出现堆栈溢出（所以我们就到了）

# iota 0 250000;;
Stack overflow during evaluation (looping recursion?).

Todo：尾递归