使用OCaml和unzip的递归

Question

我做了模式匹配，而且效果很好：

let rec unzip  l = 
    match l with
    |[] -> ([], [])
    |(x,y)::tail -> 
    let (first, second) = unzip 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) );;

但得到语法错误

Answer 1

如果您查看List.map的类型

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

您将看到它总是返回一个列表。因为您想返回一对列表，所以不能使用List.map。你可以用褶皱。或者，您可以为这对列表中的每个列表调用List.map一次。

更新

让我们只使用List.fold_left，我认为这比较容易一些。

fold_left的本质是找出一个函数来完成计算的一个步骤。到目前为止，该函数接受累积的答案，以及列表中的一个新元素。返回值是新的累积答案。如果可以定义这样的函数，则可以将其折叠到输入列表上，以获得完整的答案。

查看这一点的一种方法是，您的函数正是for语句的主体。for的主体也完成一步的计算。

假设我想要添加一个整数列表。因此，我想要的函数获得了到目前为止的累积答案( int)，这是列表中的下一个值( int)，它返回新的累计答案(两个int的和)。所以要折叠的函数是这样的：

let foldme a b = a + b

如果将其折叠到一个ints列表中，就会得到以下之和：

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

如果您想要反转一个列表，您需要一个到目前为止得到答案的函数(与列表的第一部分相反)，以及列表的一个新元素，并返回在开始时添加的新值。您想要的函数如下所示：

let foldme2 a b = b :: a

如果将其折叠在列表上，则会得到列表的反面：

# 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]

如果你能计算出一个函数，完成一步的计算，你就可以知道如何折叠。这确实需要一段时间才能做好。

Answer 2

let f (l,s) (x,y) = (x::l,y::s);;
let unzip l = List.fold_left f ([],[]) (List.rev l);;

Answer 3

您可以使用List.map两次:一次用于fst，一次用于snd。但是，我建议您花时间理解List.fold_right和List.fold_left，因为它们在许多情况下都很有用。