在OCaml中返回列表中的元素列表

Question

我刚开始接触OCaml，并尝试实现一个函数，该函数返回给定列表 x 中在列表 y 的索引处的元素列表。

例如，该函数应执行以下计算：[5,6,7,8]，[0,3] => [5,8]

我不确定如何在ML中存储临时变量，也不清楚它是如何工作的。尽管如此，我知道如何通过指定的索引从列表中查找元素。

任何想法都会受到赞赏，但我想使用递归函数并避免使用 List 模块。

- Allan Jiang

Answer 1

没有必要使用临时变量，只需使用递归！

# let rec indices xs = function
    | i :: is -> (List.nth xs i) :: indices xs is
    | [] -> []
  ;;
val indices : 'a list -> int list -> 'a list = <fun>

# indices [5;6;7;8] [0;3] ;;
- int list = [5; 8]

它通过遍历提供的每个索引来构建列表，然后将其连接到下一步返回的列表中。

希望这也被优化为尾递归形式，但我不太确定。您可能需要将其更改为正确的尾递归形式，但我会把这个决定留给您。

- mange

---

OP提到他不想使用Lisp模块（但List.nth是可以的，因为他已经有了相应的函数），但是我们仍然可以将其简化为let indices xs is is = List.map (List.nth xs) is。 - gasche

老实说：这是我第一次编写Ocaml代码，我想不出其他方法来解决它。我可能应该提到这一点，但我觉得原帖的作者应该能够理解。 - mange

确实，您的解决方案很好（并且尊重了OP的愿望，希望有一个真正的实现而不是一个stdlib技巧）。它与我建议的List.map调用完全等效--提供额外的信息。 - gasche

Answer 2

我被诱惑了，实现了我建议给@ftk的拉链解决方案。

(* A 'zipper' on the data structure "foo" is a derived data structure
   that represents a position in the data structure "foo", that can be
   filled with an element. You can think of this as a "cursor" on some
   element in the structure, that can moved in various directions to
   point to other elements of the structure. If the structure "foo"
   does not have random access, keeping a zipper allows to access the
   pointed element quickly (instead of having to look at it from the
   top of the structure again each time); its neighbors can be
   acccessed as well by moving the zipper.

   A cursor on a list has this form:

        cursor
          v
   [a; b; c; d; e; f]

   It can be represented as a value of type
     'a list * 'a * 'a list

   where the first list denotes the element before the cursor, and the
   second the elements after it. To be able to access the left
   neighbor of the cursor in constant time, we store the left elements
   in reverse order (rightmost first), so the zipper actually is

   ([b; a], c, [d; e; f])

   Zippers can be adapted to lot of data structures, including in
   particular trees. There are neat ways to define them as the
   "derivative" (in a calculus-like sense) of datatypes. See
   http://en.wikipedia.org/wiki/Zipper_(data_structure) for more
   information.
*)
let move_right = function
  | (left, x, x' :: right) -> (x :: left, x', right)
  | (_, _, []) -> raise Not_found

let move_left = function
  | (x' :: left, x, right) -> (left, x', x :: right)
  | ([], _, _) -> raise Not_found

let elem (left, e, right) = e

(* zipper of a list *)
let zipper = function
  | [] -> raise Not_found
  | x :: xs -> ([], x, xs)

let rec iterate f x = function
  | 0 -> x
  | n -> iterate f (f x) (n - 1)

let get_all data indices =
  let get_next index (pos, zip, acc) =
    let zip' =
      let move = if index < pos then move_left else move_right in
      try iterate move zip (abs (index - pos))
      with Not_found -> invalid_arg ("invalid index " ^ string_of_int index) in
    (index, zip', elem zip' :: acc) in
  let (_pos, _zip, result) =
    List.fold_right get_next indices (0, zipper data, []) in
  result

使用示例：

# get_all [0;2;4;6;8;10] [2;0;1;4];;
- : int list = [4; 0; 2; 8]
# get_all [0;2;4;6;8;10] [2;0;1;6;4];;
Exception: Invalid_argument "invalid index 6".

如果获取元素的列表很大，使用List.map (List.nth data)相比之下会明显更快：

let slow_get_all data indices = List.map (List.nth data) indices

let init n = Array.to_list (Array.init n (fun i -> i))
let data = init 100_000
let indices = List.map (( * ) 100) (init 1000)

(* some seconds *)
let _ = slow_get_all data indices

(* immediate *)
let _ = get_all data indices

当然，这只是一种练习，在实践中，如果性能很重要，您将把数据转换为更有效的数据结构，以便进行随机访问，例如数组。

- gasche

Answer 3

mange的回答很好地诠释了函数编程的威力。让我重申一下它的要点：不需要临时变量，只需使用递归。

如果你想摆脱最后一个List库调用，你可以：

1. 使用mange的indices函数并重新实现List.nth函数。这并不是很有趣，你可能更喜欢避免在每个y列表元素中对x列表进行系统性重新扫描。

2. 使用递归函数同时扫描x和y列表。例如，你可能想：

   • 弹出x列表的元素，次数等于y列表的第一个元素的值。
   • 在剩余的x列表中，保留第一个元素，弹出y的头部，并继续处理x和y的剩余部分。

我将把通常充满魔鬼的细节留给你自己去处理。

- ftk

---

如果要获取的索引不是有序的，第二种方法将如何运作？（当然，您可以先对它们进行排序，或者使用拉链或左列表而不仅仅是删除元素。） - gasche

@gasche：是的，索引需要排序，代码可能会与@winitzki的相似。但考虑到“作业”标签，我有点担心提供完整解决方案。哦，还有很棒的拉链解决方案！ - ftk

Answer 4

你需要一个函数来处理两个列表；第二个列表提供了第一个列表的索引。有两种可能性：第二个列表按升序排序，或者第二个列表没有任何排序。如果第二个列表已经排序，那么你的函数将会更加高效。这是因为可以从左到右有效地遍历列表，但是根据给定索引访问元素并不快速。

无论如何，都可以使用尾递归解决方案。（我怀疑这是一道作业题……）

关键在于不使用任何临时变量，而是在遍历列表时构建结果。用数学归纳法思考问题。归纳基础是什么？空索引列表给出空结果。归纳步骤是什么？从第二个列表中取出下一个给定的索引，将第一个列表中的一个元素附加到结果中，并假设（通过归纳）所有其他索引都将被正确处理。

如果第二个列表按升序排序且没有重复元素，则可以执行以下操作。 indices_tr 是一个尾递归函数，它有四个参数; result 是先前累积的结果列表，xs 是第一个列表的剩余部分，n 是该列表中的当前索引，is 是索引列表的剩余部分。

let indices xs is = 
 let rec indices_tr result (x::xs) n = function
   | [] -> result
   | i::is when i==n -> indices_tr (x::result) xs (n+1) is
   | is -> indices_tr result xs (n+1) is
 in
 indices_tr [] xs 0 is
;;

有一个警告，即空列表未被处理。

结果是一个反向顺序的列表：

 # indices [1;3;5;7] [0;1;2];;
 - : int list = [5; 3; 1]

使用纯尾递归解决方案并不能让你做得更好；当然，你可以将List.rev应用于它。

- winitzki