Блог

У меня есть некоторый код, написанный на OCaml, где я пытаюсь создать функцию, которая принимает список и сортирует его с помощью сортировки слиянием.

 let rec msort ls =
   let rec split lst (l1,l2) = match lst with
   | [] -> (l1,l2)
   | h::t -> split t (l2,h::l1) in
   
   let merge l1 l2 =  
      let rec mergemerge l1 l2 acc = match (l1,l2) with
      | (_,[]) -> l1
      | ([],_) -> l2
      | [], [] -> acc
      | (h1::t1,h2::t2) -> if h1 < h2 then mergemerge t1 l2 (h1 :: acc)
      else mergemerge l1 t2 (h2 :: acc)
   in List.rev (mergemerge l1 l2 [])
  in 
let (l1,l2) = 
split ls ([],[]) in merge (msort l1) (msort l2);;
  

Когда я пытаюсь скомпилировать код, он говорит «Переполнение стека во время вычисления (циклическая рекурсия?)». Мне интересно, как изменить тело, чтобы оно не повторялось бесконечно, и интересно, как и где я бы добавил базовые варианты в тело. Спасибо!

Ваша функция вызывает себя рекурсивно независимо от того, как выглядит список ввода. Таким образом, это приведет к бесконечной рекурсии.

Как вы говорите, вам нужно проверить базовый вариант.

Базовый вариант для этой функции довольно легко увидеть: есть ли какие-либо входные списки, которые уже отсортированы? Да, пустой список и список, содержащий только один элемент, уже отсортированы.

Добавьте в if ... then ... else качестве самого внешнего выражения msort . Он должен протестировать базовый вариант и вернуть очевидный результат в этом случае. В других случаях он должен делать то, что он делает сейчас.