Объединяя два списка поочередно

Question

Напишите функцию, которая объединяет два предоставленных списка. Элементы в списке вывода должны чередоваться. Вы не должны использовать библиотечные функции (например, «length», «reverse», «append») со сложностью, превышающей O (1).

Мой код:

let rec zip(aList, bList) list = 
let rec first(aLst, bLst) list = 
    if(aLst = [] && bLst = []) then []
    else if(aLst = []) then second(aLst,bLst)
     else aLst.hd :: second(aLst.tl, bLst)

 let rec second(aLst, bLst) list = 
    if(aLst = [] && bLst = []) then []
    else if(bLst = []) then first(aLst,bLst)
    else bLst.hd :: first(aLst, bLst.tl);;

zip([1;2;3;4;5], [-6]);;
zip([1;2;3;4;5],[]);;
zip([-6],[1;2;3;4;5]);;

Проблема:

let rec second(aLst, bLst) list =

Ошибка: синтаксическая ошибка

Я также боюсь rec - это будет работать правильно?

Answer 1

Синтаксис для вложенного let:

let v = expr0 in expr

Вы забыли как in, так и окончательный expr.

let rec zip(aList, bList) list = 
  let rec first(aLst, bLst) list = 
    if(aLst = [] && bLst = []) then []
    else if(aLst = []) then second(aLst,bLst)
     else aLst.hd :: second(aLst.tl, bLst)
  in
  let rec second(aLst, bLst) list = 
    if(aLst = [] && bLst = []) then []
    else if(bLst = []) then first(aLst,bLst)
    else bLst.hd :: first(aLst, bLst.tl)
  in
  first (aLst, bLst)
;;

Следующая проблема заключается в том, что first иsecond являются взаимно рекурсивными. Для этого необходимо использовать and:

let rec zip(aList, bList) list = 
  let rec first(aLst, bLst) list = 
    if(aLst = [] && bLst = []) then []
    else if(aLst = []) then second(aLst,bLst)
     else aLst.hd :: second(aLst.tl, bLst)
  and second(aLst, bLst) list = 
    if(aLst = [] && bLst = []) then []
    else if(bLst = []) then first(aLst,bLst)
    else bLst.hd :: first(aLst, bLst.tl)
  in
  first (aLst, bLst)
;;

Что дальше с (aLst, bLst) list? Какой «список» должен быть там? Удалите их через доску.

И последние списки ocaml не являются объектами. У Ocaml есть объекты, но методы вызываются с #. Также нет списков записей, которые имеют ярлыки hd и tl. Так что aLst.hd не имеет смысла. Вместо этого вы должны использовать List.hd aLst. Еще лучше было бы сопоставление с образцом, но вы, кажется, еще не узнали об этом.

Соберите все это вместе, и вы получите:

let rec zip(aList, bList) = 
  let rec first(aLst, bLst) = 
    if(aLst = [] && bLst = []) then []
    else if(aLst = []) then second(aLst,bLst)
     else List.hd aLst :: second(List.tl aLst, bLst)
  and second(aLst, bLst) = 
    if(aLst = [] && bLst = []) then []
    else if(bLst = []) then first(aLst,bLst)
    else List.hd bLst :: first(aLst, List.tl bLst)
  in
  first (aList, bList)
;;

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

Answer 2

Обычным рекурсивным шаблоном для чередования является замена аргументов в рекурсивных вызовах, например.

let rec zip a b =
  match a with
  | [] -> b
  | x :: a' -> x :: zip b a'                      (* swap arguments *)

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