Рекурсивная хвостом сортировка слиянием в OCaml
Я пытаюсь реализовать рекурсивную хвостом сортирующую список функцию в 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 это быть впущенным привязка sort функция?
2 ответа
Выражение
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)
Сортировка слиянием по своей природе не является хвостовой рекурсивной. Сортировка требует двух рекурсивных вызовов, а при любом выполнении любой функции не более одного динамического вызова может находиться в хвостовой позиции. (split также вызывается из нехвостовой позиции, но поскольку он должен использовать постоянное пространство стека, это должно быть нормально).
Убедитесь, что вы используете последнюю версию OCaml. В версиях 3.08 и старше, List.rev мог переполнить стек. Эта проблема исправлена в версии 3.10. Используя версию 3.10.2, я могу отсортировать список из десяти миллионов элементов с помощью вашего кода. Это занимает пару минут, но я не уничтожаю стек. Так что я надеюсь, что ваша проблема просто в том, что у вас старая версия OCaml.
Если нет, то хорошим следующим шагом будет установка переменной окружения
OCAMLRUNPARAM=b=1
, которая даст трассировку стека, когда вы сдуваете стек.
Я также хотел бы знать длину массивов, которые вы сортируете; хотя сортировка слиянием не может быть хвостовой рекурсивной, ее нехвостовая природа должна стоить вам логарифмического стекового пространства.
Если вам нужно отсортировать более 10 миллионов элементов, возможно, вам стоит рассмотреть другой алгоритм? Или, если хотите, вы можете вручную CPS-преобразовать mergesort, что даст хвостовую рекурсивную версию за счет выделения конъюнкций на куче. Но я думаю, что в этом не будет необходимости.