0

重要提示：我只被允许使用List.head，List.tail并且List.length 没有 List.map List.rev ......等

只有 List.hd、List.tl 和 List.length

仅当列表的长度为奇数时，如何在列表列表中复制列表的元素

这是我尝试过的代码：

let rec listes_paires x = 
  if x=[] then [] 
  else [List.hd (List.hd x)] 
       @ (List.tl (List.hd x)) 
       @ listes_paires (List.tl x);;

(* editor's note: I don't know where this line is supposed to go*)
if List.length mod 2 = 1 then []

举个例子：

lists_odd [[]; [1];[1;2];[1;2;3];[];[5;4;3;2;1]];;

返回

[[]; [1; 1]; [1; 2]; [1; 2; 3; 1; 2; 3]; []; [5; 4; 3; 2; 1; 5; 4; 3; 2; 1]]

任何帮助将不胜感激

谢谢你们

4

1 回答 1

5

看起来您的练习是关于在列表上编写递归函数，以便您可以学习如何编写函数，如List.length、List.filter等。

从最简单的递归函数开始，即计算列表长度的函数。回想一下，您可以对输入列表结构进行模式匹配并对其做出决定，例如，

let rec length xs = match xs with
  | [] -> 0 (* the empty list has size zero *)
  | hd :: tl -> 
  (* here you can call `length` and it will return you 
     the length of the list hing how you can use it to 
     compute the length of the list that is made of `tl` 
     prepended with `hd` *)
   ???

诀窍是首先编写简单的案例，然后假设您的递归函数已经工作，然后编写复杂的案例。不要想太多，也不要试图计算递归将如何在你的脑海中工作。它会让人受伤:) 只需正确编写基本案例（简单案例）并确保递归调用函数并正确组合结果，同时假设它正常工作。它被称为归纳原理，它有效，相信我:)

上面的length函数很简单，因为它生成一个整数作为输出，而且构建它非常容易，例如，您可以使用+从其他整数构建一个新整数，这是我们在生命早期就学到的东西，所以它不会不要让我们吃惊。但是如果我们想要构建一些更复杂的东西（事实上它并没有更复杂，只是对我们来说不太常见），例如列表数据结构，该怎么办？好吧，它是一样的，我们可以只使用::而不是+在我们的结果中添加东西。

因此，让我们尝试编写filter将在输入列表上递归并从满足给定谓词的元素构建一个新列表的函数，

let rec filter xs keep = match xs with
 | [] -> (* the simple case - no elements nothing to filter *)
  []
 | x :: xs -> 
   (* we call filter and it returns the correctly filtered list *)
   let filtered = filter xs keep in
   (* now we need to decide what to do with `x` *)
   if keep x then (* how to build a list from `x` and `filtered`?*)
   else filtered (* keep filtering *)

学习递归函数的下一个技巧是如何使用添加额外状态的辅助函数（也称为累加器）。例如，rev反转列表的函数最好用一个额外的累加器来定义。是的，没有它我们可以很容易地定义它，

let rec rev xs = match xs with
  | [] -> []
  | x :: xs -> rev xs @ [x]

但这是一个非常糟糕的主意，因为@操作员将不得不走到第一个列表的末尾并在路上构建一个全新的列表以仅添加一个元素。那就是我们的rev实现将具有二次性能，即，对于 n 个元素的列表，它将构建 n 个列表，每个列表中有 n 个元素，只是删除其中的大部分。所以更有效的实现将使用一个辅助函数，它有一个额外的参数，一个累加器，

let rev xs = 
  (* we will pump elements from xs to ys *)
  let rec loop xs ys = match xs with
    | [] -> ys (* nothing more to pump *)
    | x :: xs -> 
      let ys = (* push y to ys *) in
      (* continue pumping *) in
  loop xs []

这个技巧也将帮助您实现您的任务，因为您需要按元素的位置进行过滤。这意味着您的递归函数需要一个额外的状态来计算位置（通过列表元素的每个递归步骤递增一）。因此，您将需要一个带有该计数器额外参数的辅助函数。

于 2021-08-04T19:53:23.437 回答