使用 OCaml 递归并解压缩

Question

我进行了模式匹配，效果很好：

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

但是我如何使用 map 或 fold right 来做到这一点（仅提供提示，请不要告诉我实际如何操作）

我在想一些事情：

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>

您会发现它总是 return 一个列表。既然你想 return 一对列表，你就不能使用 List.map。你可以使用折叠。或者您可以为该对中的每个列表调用一次 List.map。

更新

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

fold_left 的本质是找出一个函数来执行您的计算的一个步骤。该函数采用到目前为止累积的答案，以及列表的一个新元素。 return 值是新的累积答案。如果你可以定义这样一个函数，你可以将它折叠到输入列表上以获得完整的答案。

一种看待这个问题的方法是，您的函数正是 for 语句的主体。 for 的主体也执行一步计算。

假设我想添加一个整数列表。所以我想要的函数采用到目前为止的累积答案（一个整数），列表中的下一个值（一个整数），它 return 是新的累积答案（两个整数的总和）。所以要折叠的函数看起来像这样：

let foldme a b = a + b

如果你将它折叠到一个整数列表上，你会得到总和：

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

如果你想反转列表，你需要一个函数来获取到目前为止的答案（列表第一部分的反转）和列表的新元素，returns与开始时添加的新值相反。所以你想要的功能看起来像这样：

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

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

Answer 3

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

Recursion using OCaml and unzip