使用OCaml递归并解压缩 [英] Recursion using OCaml and unzip

问题描述

  let rec unzip l = 
 match l with 
 | []  - > （[]，[]）
 |（x，y）:: tail  - > 
 let（first，second）= unbip tail in 
（x :: first，y :: second）
  

但是我怎样才能做到这一点使用地图或折叠权（提示只请不要告诉我如何实际做到这一点）

我正在思考一些问题：

  let unzip：（'a *'b）list  - > 'a list *'b list = let（first，second）= map（fun（x，y） - >（x :: first，y :: second））;; 
  

但是出现语法错误

解决方案

如果您查看 List.map 类型：

 ＃List.map ;; 
  -  :('a  - >'b） - > '列表 - > 'b list =< fun> 
  

您会看到它总是返回一个列表。既然你想返回一对列表，你不能使用 List.map 。你可以使用折叠。或者，您可以为每个列表中的每个列表调用 List.map 一次。

更新

让我们使用 List.fold_left ，我认为它更容易一些。

fold_left 的本质是找出一个计算一步的函数。该函数到目前为止累积了答案，并且列表中有一个新元素。返回值是新的累积答案。如果你可以定义这样一个函数，你可以将它折叠在输入列表中以获得完整答案。

查看这个函数的一种方法就是你的函数就是将作为语句的的主体出现。 的主体也可以执行一个计算步骤。

假设我想添加一个列表整数。因此，我期望的函数将迄今为止的累计答案（一个int），列表中的下一个值（一个int）取回，并返回新的累计答案（两个整数的和）。因此，要折叠的功能如下所示：

  let foldme ab = a + b 
  
 <$ p $ <$ p 
 
 
 $ b pre> ＃let foldme ab = a + b ;; 
 val foldme：int  - > int  - > int =< fun> 
＃List.fold_left foldme 0 [3; 5; 7; 11]; 
  - ：int = 26 
  

如果您想要反转列表，到目前为止的答案（列表第一部分的反向）和列表的新元素，并返回与开始时添加的新值相反的结果。所以你想要的功能如下所示：

  let foldme2 ab = b :: a 
  

如果您将其放在列表中，您会得到列表的反面：



 ＃let foldme2 ab = b :: a ;; 
 val foldme2：'列表 - > 'a  - > '一个列表=< fun> 
＃List.fold_left foldme2 [] [4; 5; 6; 7] ;; 
  - ：int list = [7; 6; 5; 4] 
  

如果您可以计算一个可以执行一步计算的函数，那么您可以计算出如何做褶皱。它需要一段时间才能完成。

I did pattern matching, and it's working just fine:

let rec unzip  l = 
    match l with
    |[] -> ([], [])
    |(x,y)::tail -> 
    let (first, second) = unzip tail in 
      (x::first, y::second)

but how would I do this using map or fold right (tips only please don't tell me how to actually do it)

I was thinking something along the lines of:

let unzip : ('a * 'b) list -> 'a list * 'b list = let (first,second) = map (fun (x,y) -> (x::first, y::second) );;

but getting syntax error

解决方案

If you look at the type of List.map:

# List.map;;
- : ('a -> 'b) -> 'a list -> 'b list = <fun>

You'll see that it always returns a list. Since you want to return a pair of lists, you can't use List.map. You can use a fold. Or you could call List.map once for each list in the pair.

Update

Let's just work with List.fold_left, which I think is a little easier.

The essence of fold_left is to figure out a function that does one step of your computation. The function takes the accumulated answer so far, and one new element of the list. The return value is the new accumulated answer. If you can define such a function, you can fold it over the input list to get your full answer.

One way to look at this is that your function is exactly what would appear as the body of a for statement. The body of a for also does one step of a computation.

Let's say I want to add a list of integers. So my desired function takes the accumulated answer so far (an int), the next value from the list (an int), and it returns the new accumulated answer (the sum of the two ints). So the function to be folded looks like this:

let foldme a b = a + b

If you fold this over a list of ints you get the sum:

# let foldme a b = a + b;;
val foldme : int -> int -> int = <fun>
# List.fold_left foldme 0 [3; 5; 7; 11];;
- : int = 26

If you wanted to reverse a list, you want a function that takes the answer so far (reverse of the first part of the list), and a new element of the list, and returns the reverse with the new value added at the beginning. So the function you want looks like this:

let foldme2 a b = b :: a

If you fold this over a list, you get the reverse of the list:

# let foldme2 a b = b :: a;;
val foldme2 : 'a list -> 'a -> 'a list = <fun>
# List.fold_left foldme2 [] [4; 5; 6; 7];;
- : int list = [7; 6; 5; 4]

If you can figure out a function that does one step of your computation, you can figure out how to do folds. It does take a while to get good at it.

这篇关于使用OCaml递归并解压缩的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！