Tail-рекурсивная сортировка слиянием в OCaml

Question

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

let tailrec_merge_sort l = 
    let split l = 
    let rec _split source left right = 
     match source with 
     | [] -> (left, right) 
     | head :: tail -> _split tail right (head :: left) 
    in _split l [] [] 
    in 

    let merge l1 l2 = 
    let rec _merge l1 l2 result = 
     match l1, l2 with 
     | [], [] -> result 
     | [], h :: t | h :: t, [] -> _merge [] t (h :: result) 
     | h1 :: t1, h2 :: t2 -> 
      if h1 < h2 then _merge t1 l2 (h1 :: result) 
      else   _merge l1 t2 (h2 :: result) 
    in List.rev (_merge l1 l2 []) 
    in 

    let rec sort = function 
    | [] -> [] 
    | [a] -> [a] 
    | list -> let left, right = split list in merge (sort left) (sort right) 
    in sort l 
;; 

Тем не менее, кажется, что это на самом деле не является хвостовым рекурсивным, так как я сталкиваюсь с ошибкой «Переполнение стека во время оценки (циклическая рекурсия?)».

Не могли бы вы помочь мне обнаружить не хвостовой рекурсивный вызов в этом коде? Я много искал, не найдя его. Cout это будет привязка let в функции sort?

Answer 1

Выражение

merge (sort left) (sort right) 

не хвостовой рекурсией; он вызывает как (сортировка слева), так и (сортировка справа) рекурсивно, пока в вызове остаётся работа (слияние).

Я думаю, что вы можете это исправить с дополнительным параметром продолжения:

let rec sort l k = 
    match l with 
    | [] -> k [] 
    | [a] -> k [a] 
    | list -> let left, right = split list in sort left (fun leftR -> sort right (fun rightR -> k (merge leftR rightR))) 
    in sort l (fun x -> x) 

Answer 2

Merge сортировать по своей сути не хвостовой рекурсией. Для сортировки требуется два рекурсивных вызовах, а при любом выполнении любой функции не более один динамический вызов может быть в хвостовом положении. (split также вызывается из положения, отличного от хвоста, но поскольку он должен использовать постоянное пространство стека, которое должно быть ОК).

Убедитесь, что используете последнюю версию OCaml. В версиях 3.08 и старше List.rev может взорвать стек. Эта проблема исправлена ​​в версии 3.10. Используя версию 3.10.2, я могу отсортировать список из десяти миллионов элементов, используя ваш код. Это займет пару минут, но я не взорву стек. Поэтому я надеюсь, что ваша проблема просто в том, что у вас есть старая версия OCaml.

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

OCAMLRUNPARAM=b=1 

, который даст трассировки стека, когда вы дуете стек.

Я также хотел бы знать длину массивов, которые вы сортируете; хотя сортировка слияния не может быть хвостовой рекурсивной, ее не-хвостовая природа должна стоить вам logarithmic стек пространства.

Если вам нужно отсортировать более 10 миллионов элементов, возможно, вам стоит посмотреть на другой алгоритм? Или, если вы хотите, вы можете CPS-convert mergesort вручную, что даст хвостовую рекурсивную версию за счет выделения контуров в куче. Но я предполагаю, что это не понадобится.