我在语言OCaml的两个问题上遇到困难

html5 • • 问答

重要提示：我只允许使用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]]

任何帮助将不胜感激

谢谢你们

回答

看起来您的练习是关于在列表上编写递归函数，以便您可以学习如何编写诸如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 []

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

以上是我在语言OCaml的两个问题上遇到困难的全部内容。
THE END
分享
二维码
< <上一篇
下一篇>>