Как сжать каждый отдельный элемент из двух списков в один список с помощью 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

Если ваш список результатов должен содержать элементы, состоящие из элементов обоих подсписков, то вам, очевидно, придется деструктурировать каждый подсписок на каждой итерации.

Если гарантируется, что списки имеют одинаковую длину, решение может быть простым:

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

Но этот не является хвост-рекурсивным, что, очевидно, не хорошо. Вторая неоптимальная вещь - это реконструкция набора списков на каждой итерации (я новичок ie в OCaml, так что скорее всего компилятор достаточно умен, чтобы избежать ненужных распределений, но все же ...). Исправление обоих fl aws тоже тривиально:

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 2

В дополнение к другим упомянутым решениям ocaml-4.08 позволяет вам предоставлять операторов let + и и +, которые будут суммировать список по сумме, где вы могли бы подумать об использовании аппликативов. Является ли это улучшением по их мнению, в глазах смотрящего:

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 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 type.

В вашем коде должно быть что-то вроде (x,y)::list.

Кроме того, pairlists не является рекурсивным и не должен быть объявлен как таковой, только zip является рекурсивным. Конец вашей функции должен быть таким (иначе zip не имеет никакого эффекта):

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