Вы объявили merge_sorted как функцию типа int list -> int list -> int list или функцию, которая принимает два списка int в качестве параметров и возвращает другой список int.
Проблема, с которой вы сталкиваетесь, заключается в том, что вы вызываете merge_sorted с тремя int list аргументами:
h1::t1, h2::t2 -> if h1 < h2 then merge_sorted t1 t2 (h1 :: end_list) else merge_sorted t1 t2 h2::end_list, h1::end_list
в частности, merge_sorted t1 t2 (h1 :: end_list) . Вы не предусмотрели список результатов в определении своей функции.
Вы захотите изменить определение своей функции, возможно, так:
let rec merge_sorted l1 l2 results =
(* code code code *)
Относительно вашего второго вопроса, приличный набор учебников можно найти здесь .
EDIT
В ответ на ваш комментарий-
Во-первых, оператор :: служит двум целям. Во-первых, он создает новый список с новой головой и существующим хвостом - 1 :: [2] приводит к [1; 2]. Во-вторых, он разбирает существующие списки во время сопоставления с образцом - match [1; 2] with x :: xs свяжет x с 1 и y с [2].
С учетом этого, в вашем подходе есть несколько вещей, которые отлично работают в Java, но не будут работать вообще в OCaml. Во-первых, вы повторно объявляете end_list как пустой список при каждом рекурсивном вызове вашей функции.
Во-вторых, поскольку у вас конкатенация списка в той же строке, что и рекурсивный вызов merge_sorted, компилятор будет (не имеет иного выбора) думать, что вы задаете третий вызов функции. Что вы, вероятно, имели в виду:
h1::t1, h2::t2 -> if h1 < h2 then
merge_sorted t1 t2
h1 :: end_list
else
merge_sorted t1 t2
h2 :: end_list
h1 :: end_list
НО! Это не ваше решение, читайте дальше.
В-третьих, и, что гораздо важнее, OCaml не работает таким образом. По умолчанию списки OCaml (и все переменные, на самом деле) являются неизменяемыми, то есть, если вы привязали значение к одному, вы не сможете его изменить. Когда вы говорите (h1 :: end_list), вы не меняете end-list; то, что вы на самом деле делаете, - это создание нового списка, в котором h1 является его головой, а end_list - его хвостом. Поскольку все это в одной строке, компилятор считает, что вы делаете эквивалент merge_sorted(t1, t2, new List(h1, end_list)) в Java-земле, где вы определили merge_sorted(List t1, List t2).
Поскольку вы не можете изменить свой список на месте, функциональные языки этой полосы имеют разные идиомы для обработки списка. В этом случае большинство функциональных программистов определили бы свою функцию, чтобы получить дополнительный аргумент аккумулятор . Например:
let rec map f data acc =
match data with
| [] -> List.rev acc
| x :: xs -> map f xs ((f x) :: acc);;
map (fun x -> x + 1) [1; 2; 3;] [];; (* yields [2; 3; 4] *)
Это каноническая функция map, которая принимает список и функцию, применяет каждый элемент в списке к этой функции и возвращает новый список, содержащий результаты. Как вы можете видеть, результаты применения каждого элемента от data до f сохраняются в acc и , результат передается следующему вызову , который должен быть возвращен, когда data пустой. Таким образом, мы можем выполнить серию модификаций списка без необходимости изменять переменную.
Если вам не нравится дополнительный аргумент в сигнатуре функции, вы можете спрятать его внутри вложенной функции следующим образом:
let map f data =
let rec loop d acc =
match d with
| [] -> List.rev acc
| x :: xs -> loop xs ((f x) :: acc)
in
loop data []
Я надеюсь, что это имеет какой-то смысл для вас - переход от императивного к функциональному идиомам может быть действительно изнурительным, а неизменность может показаться жестоким и произвольным ограничением для новичков в этом - я обещаю, что преимущества и красота функциональных программирование будет проявляться перед вами, если вы будете придерживаться его!