OCaml —返回包含该列表尾部的列表

| 对于[1;2;3;4;5]，我想返回[[1;2;3;4;5];[2;3;4;5];[3;4;5;];[4;5];[5];[]] 我正在尝试使用列表库，但不确定如何使用。到目前为止，我知道我必须使用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

编辑：对不起，我为函数返回指定的内容不正确。只是使用正确的输出进行了更新。

已邀请:

4 个回复

薄扩络拜

正如我在评论中所说，这些不是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]; []]

才脊烽馈低

就内置函数而言，没有好的方法可以编写该函数。您在问题中给出的答案很好，但是不注释类型并使用function会更惯用：

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

其他语言（例如F＃）提供List.unfold函数，可以用tails编写。

草票

啊，这是在原始列表上积累的古老技巧，可以将ѭ10转化为类同化。只需使用ѭ12just模块上的函数，就无需显式递归即可完成此操作：

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]; []]

尾部是输入列表的实际结构尾部，因此ѭ15。

贡炮逗握惫

\“不使用递归\” ...为什么？递归是一个有用的工具，即使在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

最后，可以使用延续版本破坏您的大脑，但是我不记得确切的代码。大致上，延续等效于直接版本的“累加器”。

要回复问题请先登录或注册

OCaml —返回包含该列表尾部的列表

4 个回复

发起人

ocaml

问题状态

OCaml —返回包含该列表尾部的列表

与内容相关的链接

4 个回复

发起人

ocaml

问题状态