如何使用 OCaml 将两个列表中的每个单独元素压缩到一个列表中

Question

如果我有一个元组的输入，其中包含两个相同长度的整数列表，并且我希望我的输出是这两个列表压缩的列表，那么从元组中提取这两个列表后，如何将每个单独的元素压缩到一份清单？例如，如果我的输入是twolists= ([1;2;3], [4;5;6])，那么我希望我的输出是[(1,4); (2,5); (3,6)]。如何压缩每个元素并将其添加到我的输出中？ 函数名称和类型如下：

let rec pairlists twolists = ...

val pairlists : 'a list * 'b list -> ('a * 'b) list = fun

到目前为止我已经：

let rec pairlists twolists = 
  let (l1, l2) = twolists in
  let rec zip (l1,l2) =
    match l1 with 
    |[] -> l2
    |x :: xs -> x :: zip(l2, xs) in
  twolists ;;

但这显然不是我想要的。

Answer 1

您在寻找List.combine吗？

val 组合：'a 列表 -> 'b 列表 -> ('a * 'b) 列表

将一对列表转换为一对列表：combine [a1; ...;一个] [b1; ...; bn] 是 [(a1,b1); ...; (an,bn)]。

如果两个列表的长度不同，则引发 Invalid_argument。不是尾递归。

Answer 2

如果您的结果列表应包含由两个子列表的元素组成的元素，那么您显然必须在每次迭代时解构每个子列表。

如果保证列表具有相同的长度，解决方案可以很简单：

let rec zip paired_lists =
  match paired_lists with
  | [], [] -> []
  | h1::t1, h2::t2 -> (h1, h2)::(zip (t1, t2))
  | _, _ -> failwith "oops, the lists seems to have different lengths"
;;

zip ([1;2;3], [4;5;6]);;
- : (int * int) list = [(1, 4); (2, 5); (3, 6)]

但是这个不是尾递归，这显然不好。第二个次优的事情是每次迭代时重建列表元组（我是 OCaml 的新手，所以编译器很可能足够聪明，可以避免不必要的分配，但仍然......）。修复这两个缺陷也很简单：

let zip_tr paired_lists =
  let list1, list2 = paired_lists in
  let rec aux l1 l2 acc =
    match l1, l2 with
    | [], [] -> List.rev acc
    | h1::t1, h2::t2 -> aux t1 t2 (h1, h2)::acc
    | _, _ -> failwith "oops, the lists seems to have different lengths"
  in aux list1 list2 []
;;

zip_tr ([1;2;3], [4;5;6]);;
- : (int * int) list = [(1, 4); (2, 5); (3, 6)]

Answer 3

您的代码签名与预期签名不匹配：

line 2, characters 11-13:
Warning 26: unused variable l2.
Line 2, characters 7-9:
Warning 26: unused variable l1.
val pairlists : 'a list * 'a list -> 'a list = <fun>

事实上，两种可能的匹配都会返回

'a list

（这是 l2）或

x::zip...

，这也是

'a

类型的列表。

您的代码中应该有类似

(x,y)::list

的内容。

此外，

pairlists

不是递归的，不需要这样声明，只有

zip

是递归的。 你的函数的结尾应该是这样的（否则 zip 没有效果）：

....
let rec zip (l1,l2) =
match l1 with 
|[] -> l2
|x :: xs -> x :: zip(l2, xs) in
zip twolists ;;

Answer 4

除了提到的其他解决方案之外，ocaml-4.08 及以后版本还允许您提供 let+ 和 and+ 运算符，它们将按总和方式压缩列表，否则您可能会考虑使用应用程序。是否对他们有所改进，仁者见仁智者见智：

let (let+) list f = List.map f list

let (and+) a b =
  let rec loop first second =
    match first,second with
      first_hd::first_tl,second_hd::second_tl ->
       (first_hd,second_hd)::(loop first_tl second_tl)
    | _ -> []
  in
  loop a b

let pairlists = function
    first,second ->
     let+ elt1 = first
     and+ elt2 = second in
     [elt1 ; elt2]

(* example *)
let () =
  let res = pairlists ([1;2;3], [4;5;6]) in
  List.iter
    (fun list -> List.iter (fun i -> Printf.printf "%d " i) list ;
                 print_endline "")
    res

如果您使用应用程序，这里通过比较是更传统的方法

let pure x = [x]

let (<*>) aps args =
  List.concat (List.map (fun f -> List.map (fun x -> f x) args) aps)

let (<|>) aps args =
  let rec loop args_rest aps_rest =
    match args_rest,aps_rest with
      args_hd::args_tl,aps_hd::aps_tl ->
       (aps_hd args_hd)::(loop args_tl aps_tl)
    | _ -> []
  in
  loop args aps

let pairlists = function
    first,second ->
     let two_list a b = a :: [b] in
     pure two_list <*> first <|> second

(* example *)
let () =
  let res = pairlists ([1;2;3], [4;5;6]) in
  List.iter
    (fun list -> List.iter (fun i -> Printf.printf "%d " i) list ;
                 print_endline "")
    res

Answer 5

另一种方法是懒惰和尾递归，使用序列。

# let rec seq_pairs lst1 lst2 () =
    match lst1, lst2 with
    | [], [] -> Seq.Nil
    | x::xs, y::ys -> Seq.Cons ((x, y), seq_pairs xs ys)
    | _, _ -> invalid_arg "lengths don't match";;
val seq_pairs : 'a list -> 'b list -> ('a * 'b) Seq.t = <fun>
# List.of_seq @@ seq_pairs [1; 2; 3] [4; 5; 6];;
- : (int * int) list = [(1, 4); (2, 5); (3, 6)]