7

我是 OCaml 的新手，我现在正在尝试实现一个函数，该函数在 listx的索引处返回给定列表的元素列表y。

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

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

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

4

4 回答 4

7

不需要临时变量，只需使用递归！

# 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]

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

希望这也被优化为尾递归形式，但我对此不太确定。您可能希望将其更改为适当的尾递归，但我将由您决定。

于 2012-03-21T05:10:12.837 回答
3

我被诱惑并实施了我向@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

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

于 2012-03-21T22:13:38.987 回答
2

mange 的回答很好地说明了函数式编程的力量。请允许我重申它的要点：不需要临时变量，只需使用 recursion。

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

  1. 使用mange的indices功能并重新实现该List.nth功能。这不是很有趣，您可能更喜欢避免系统地重新扫描x列表中的每个元素y。

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

    • 弹出列表元素的x次数与列表第一个元素的值一样多y。
    • 在剩余的列表中x，保留第一个元素，弹出 的头部，然后继续处理andy的其余部分。xy

我将把细节留给你，就像他们通常居住的魔鬼一样，由你决定。

于 2012-03-21T15:31:07.370 回答
1

您需要两个列表的功能；第二个列表为第一个列表提供索引。有两种可能：第二个列表按升序排序，或者第二个列表不按任何方式排序。如果对第二个列表进行排序，您的功能将更加高效。之所以如此，是因为可以有效地从左到右遍历列表，但随机访问具有给定索引的元素并不快。

在任何情况下，尾递归解决方案都是可能的。（我怀疑这是一个家庭作业问题......）

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

如果第二个列表按升序排序，没有重复的元素，您可以执行以下操作。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 。

于 2012-03-21T17:13:20.237 回答