通过索引访问列表中的元素

Question

在 OCaml 中，我想编写一个函数，返回列表给定索引处的元素。例如

[4;5;6] 0 -> 4

、

[4;5;6] 1 -> 5

。我知道如何递归地执行此操作，但是任何人都可以展示如何使用

fold_left

或

fold_right

来解决此问题吗？非常感谢！

Answer 1

让我们看看如何使用

fold_left

打印列表中的元素。

let print lst =
  List.fold_left 
    (fun i x -> Format.printf "%d: %d\n" i x; i + 1) 
    0 lst;

0

的初始索引作为初始值传入。每次通过我们都会产生打印一行的副作用，然后将初始值更新为

i + 1

。

结果：

# print [1;4;6;2;7];;
0: 1
1: 4
2: 6
3: 2
4: 7
- : int = 5

这很好地向我们展示了折叠在迭代列表时如何更新其累加器。

但是，如果我们要在索引处搜索值，那么我们可以使用当前索引的元组和返回值的选项类型，以防我们找不到要查找的索引。

let at idx lst = 
  List.fold_left 
    (fun i x ->
       match i with
       | (_, Some _).              -> i
       | (idx', _) when idx = idx' -> (idx', Some x)
       | (idx', _)                 -> (idx' + 1, None))
    (0, None)
    lst

我们从

0

和

None

作为初始值。对于列表中的每个项目，我们检查累加器中的选项类型值是否为

Some _

。我们不关心这个值，但如果它是 not

None

，我们就找到了我们要找的东西，不需要更新累加器。

如果累加器确实包含

None

并且当前索引与我们要查找的索引相同，则用当前值的

Some

更新累加器。索引不需要更新。

如果索引不是我们要查找的索引，请增加索引并继续。

# at 3 [1;2;3;4;5];;
- : int * int option = (3, Some 4)

但是由于我们不需要元组中的第一个元素，因此我们可以使用 let 绑定来命名我们正在查找的结果并返回该结果。

let at idx lst = 
  let (_, result) = List.fold_left 
    (fun i x ->
       match i with
       | (_, Some _)               -> i
       | (idx', _) when idx = idx' -> (idx', Some x)
       | (idx', _)                 -> (idx' + 1, None))
    (0, None)
    lst
  in
  result

现在：

# at 3 [1;2;3;4;5];;
- : int option = Some 4

看看如何实施

List.fold_left

可能会有所启发。

let rec fold_left f init lst =
  match lst with
  | []    -> init
  | x::xs -> fold_left f (f init x) xs

在

at

中，累加器元组中的

Some _

条件导致累加器值传播到折叠末尾而不更新。

---

或者，我们可以使用本地异常在找到我们正在寻找的索引后立即突破折叠。

let at idx lst = 
  let exception Early_exit of int in
  try
    let (_, result) = List.fold_left 
      (fun i x ->
         match i with
         | (_, Some _)               -> i
         | (idx', _) when idx = idx' -> raise (Early_exit x)
         | (idx', _)                 -> (idx' + 1, None))
      (0, None)
      lst
    in
    result
  with Early_exit x -> Some x

或者也许更干净一点：

let at idx lst = 
  let exception Early_exit of int in
  match List.fold_left 
    (fun i x ->
       match i with
       | (_, Some _)               -> i
       | (idx', _) when idx = idx' -> raise (Early_exit x)
       | (idx', _)                 -> (idx' + 1, None))
    (0, None)
    lst with
  | (_, result)            -> result
  | exception Early_exit x -> Some x

当然，我们现在知道，如果未引发异常

Early_exit

，则未找到索引，因此结果将始终为

None

。

let at idx lst = 
  let exception Early_exit of int in
  match List.fold_left 
    (fun i x ->
       match i with
       | (_, Some _)               -> i
       | (idx', _) when idx = idx' -> raise (Early_exit x)
       | (idx', _)                 -> (idx' + 1, None))
    (0, None)
    lst with
  | _                      -> None
  | exception Early_exit x -> Some x

和测试：

# at 3 [1;2;3;4;5];;
- : int option = Some 4

但是如果我们以这种方式使用异常，我们真的根本不需要

List.fold_left

。我们可以只使用

List.iteri

。

let at idx lst =
  let exception Found of int in
  try 
    List.iteri (fun i x -> if i = idx then raise (Found x)) lst;
    None 
  with Found x -> Some x

Answer 2

这两种折叠都可以让您按顺序访问列表的元素，同时保持某种可以自由选择的状态。不同之处在于

fold_left

从列表的开头开始并向结尾方向移动，而

fold_right

从列表的结尾处开始并向开头方向移动。

由于您的索引从列表的开头开始，我想说使用它会更容易

fold_left

。

所以，你的问题是找出某种可以维护的状态，这样当你查看整个列表时，你就知道列表的第 n 个元素是什么。

你基本上可以从问题中找出状态：你需要知道你正在查看列表中的哪个元素（这样你就知道何时到达第n个）。您需要记住第 n 个元素（如果您已经见过它），以便在到达列表末尾时可以使用它。如果您还没有看到第 n 个元素，则需要相同类型的内容作为占位符（或者您可以使用选项类型）。

您需要一个函数，它接受这样的状态（以及列表的一个元素）并生成与列表的下一个元素相关的状态。这实际上与编写循环没有太大区别，只是您需要显式地将状态作为参数传递并返回新状态作为结果。

Answer 3

当找到索引元素时，你需要一些退出机制。

exception Value of int

let get_index_value_using_fold_left l i =
  let index_value = ref 0 in
  try
    List.fold_left
      (
        fun a e ->
          if !index_value = i
          then
            raise (Value e)
          else
            (
              index_value := !index_value + 1;
              a
            )
      ) None l
  with
  | Value ans -> Some ans

let ans = get_index_value_using_fold_left [11;2;13;4;15;6;17;8;19;20;] 2

let () =
  Option.iter (fun x -> Printf.printf "%d\n" x) ans