如何从ocaml列表中获取子列表

Question

我正在查看列表文档。该库似乎没有提供 sublist 功能。

我正在尝试获取从 i 到 j 的元素列表。现在我必须将其写为：

let rec sublist list i j =
  if i > j then
    []
  else
    (List.nth list i) :: (sublist list (i+1) j)

这非常简洁，但我质疑 List.nth 的效率，因为如果它是 O(n)，我宁愿以不太简洁的方式编写它。

我想知道为什么他们不提供 List.sublist 函数，如果 List.nth 不是 O(1)，因为它是这样的很常见的操作..

Answer 1

let rec sublist b e l = 
  match l with
    [] -> failwith "sublist"
  | h :: t -> 
     let tail = if e=0 then [] else sublist (b-1) (e-1) t in
     if b>0 then tail else h :: tail
;;

sublist 3 5 [1;2;3;4;5;6;7;8;9] ;;
- : int list = [4; 5; 6]

以上或多或少是 newacct 解决方案的砍伐版本。 newacct 的解决方案分配一个中间列表（drop i list），编译器可以在 Haskell 中对其进行优化，但在 ML 中则困难得多。因此，他的版本非常适合 Haskell 函数，但对于 ML 函数来说稍显次优。两者之间的差别只是一个常数因子：都是 O(e)。 zrr 的版本是 O(length(l))，因为 List.filteri 不知道 f 仅在一段时间后返回 false，它调用它适用于 l 中的所有元素。

我不太高兴让 b 变为负数，但不这样做的版本更复杂。

如果您有兴趣，可以从众多有关森林砍伐的参考文献中找到一份：http:// /homepages.inf.ed.ac.uk/wadler/topics/deforestation.html

Answer 2

首先尝试编写 take （前 n 个项目）和 drop （除了前 n 个项目之外的所有项目）函数（就像在 Haskell 中一样）。那么 sublist ij lst 只是 take (ji) (drop i lst)

Answer 3

这比使用 OCaml 的标准库要困难一些——标准库有点稀疏。如果您使用扩展标准库之一，它会变得更容易。例如，对于 Core，您可以这样写：

let sublist list low high =
   List.filteri l ~f:(fun i _ -> i >= low && pos < high)

我想 extlib/batteries 也可以实现类似的功能。

Answer 4

虽然 Pascal 提供的答案实现了 List.sublist 的一个很好的候选者，但正确的答案是您应该更好地使用列表数组。 Array 模块实现了您可能使用的 Array.sub 函数。

虽然在许多命令式语言（例如 C++ 或 Perl）中，列表和数组之间本质上没有区别，但在 OCaml 中却不同，其中：

• 列表更适合递归处理和顺序访问，即 通常是作为递归函数参数的数组的更好候选者，并且您通常希望查看列表的所有元素。

• 数组更适合随机访问、结构更改（例如排序）或数值计算。

  数组

Answer 5

let rec sublist (lst : int list) (start : int) (stop : int) : int list =
  match lst with
  | [] -> [] 
  | x::rest when start = 0 && stop >= 0 -> x::sublist rest start (stop-1)
  | x::rest when start = 0 && stop = 0 -> sublist rest start stop
  | x::rest -> sublist rest (start-1) (stop-1)
;;

when 的作用与 if else 语句一样