OCaml -- 返回一个包含给定列表所有尾部的列表

Question

对于[1;2;3;4;5]，我想返回[[1;2;3;4;5];[2;3;4;5];[3;4;5;];[4;5];[5];[]]

我正在尝试使用List库，但我不确定该如何使用。到目前为止，我知道我必须使用List.tl来获取没有第一个元素的列表。

let rec tailsoflist (l : 'a list) : 'a list list =
  match l with
      [] -> [[]]
    | x::xs -> l::(tails xs)

我之前是用递归的方式实现的，但现在想使用列表库来实现，而不使用递归。

let tails (l : 'a list) : 'a list list

编辑：抱歉，我之前指定的函数返回值是错误的。已经更新为正确的输出。

- jlaguatan

---

在模块List中没有函数可以将列表l的尾部呈现给传递给它的函数，因此您无法获得“l的尾部”。如果您接受使用List.fold_right等构建新版本的方法，则可以获得结构上等效于l尾部的列表。 - Pascal Cuoq

请注意，根据您的问题，您提供的问题解决方案是不正确的，例如 [1..4] 不是 [1..5] 的尾部。您确定您的意思不是 [2..5] 等等吗？ - J D

@Pascal：无需放弃拖尾共享：只需将原始列表作为“fold”的一部分进行线程处理即可。 - user593999

Answer 1

如我在评论中所说，这些不是l的尾数，而是l尾数的副本：

# let tails l = List.fold_right (fun e acc -> (e::(List.hd acc))::acc) l [[]] ;;
val tails : 'a list -> 'a list list = <fun>
# tails [1; 2; 3; 4] ;;- : int list list = [[1; 2; 3; 4]; [2; 3; 4]; [3; 4]; [4]; []]

- Pascal Cuoq

---

谢谢。你能解释一下这个函数在做什么吗？ACC是如何工作的，等等。 - jlaguatan

fold_right 从右到左将累加器应用于列表中的元素。每次调用都会创建一个新的 'tail'，下一个 'tail' 是上一个 (List.hd acc) 加上当前元素 (e)。从 [] 添加 4，从 [4] 添加 3，从 [3;4] 添加 2，... - nlucaroni

Answer 2

没有好的方法可以用内置函数编写该函数。

你在问题中给出的答案是可以的，但更符合惯用法的做法是不注释类型并使用 function：

let rec tails = function
  | [] -> [[]]
  | _::xs' as xs -> xs::tails xs'

其他编程语言，例如F#，提供了一个List.unfold函数，可以用它来编写tails函数。

- J D

---

完全可以仅使用内置函数编写“tails”。 - user593999

请查看我对这个问题的回答。 - user593999

Answer 3

啊，这是在原始列表上累积以将尾部（tails）作为范畴折叠的老技巧。这是通过仅使用List模块中的函数而不进行显式递归来完成的：

let tails l = List.rev ( [] :: snd (List.fold_right
    (fun _ (t,ts) -> List.tl t, t::ts) l (l, [])) )

它会按照您的预期生成尾部：

# tails [1;2;3;4;5];;
- : int list list = [[1; 2; 3; 4; 5]; [2; 3; 4; 5]; [3; 4; 5]; [4; 5]; [5]; []]

而 tails 是输入列表的实际结构尾部，因此 List.tl l == List.hd (List.tl (tails l))。

- user593999

---

即使它非常丑陋，如果它是一个有效的反例来证明我的说法，那么请给我点个赞！ - J D

适当的tails可以更简洁地表示为 let tails l = snd (List.fold_right (fun _ (t,ts) -> List.tl t, ts @ [t]) l (l, []))。这个公式是Gibbons提出的。 - user593999

Answer 4

“不使用递归”…为什么？递归是一个有用的工具，即使在List库之外也是如此。

let rec suffixes = function
| [] -> [[]]
| hd::tl as suff -> suff :: suffixes tl

你的函数（因为使用了tails而不是tailsoflist而无法编译）返回列表的后缀。由于列表结构，计算后缀比前缀更容易。

你可以从后缀中表达出前缀：

let prefixes li = List.map List.rev (suffixes (List.rev li));;

你可以使用累加器直接实现一个版本：

let prefixes li =
  let rec pref acc = function
    | [] -> List.rev acc :: []
    | hd::tl -> List.rev acc :: pref (hd :: acc) tl
  in pref [] li

如果您想避免递归，可以使用 List.fold_left 并以此表达，但我认为这样会使问题更复杂，建议优先选择直接版本：

let prefixes li =
  let acc, res =
    List.fold_left
      (fun (acc, res) e -> (e :: acc), (List.rev acc :: res))
      ([], []) li in
  List.rev acc :: res

最后，使用延续版本可能会让你的大脑崩溃，但我不记得确切的代码。大致上，延续相当于直接版本的“累加器”。

- gasche