Coda-ricorsiva merge sort in OCaml

Question

Sto cercando di implementare un elenco di smistamento funzione ricorsiva in coda in OCaml, e mi è venuta in mente il seguente codice:

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 
;; 

Eppure sembra che essa non è in realtà in coda ricorsiva, dal momento che si verifica un errore "Stack overflow durante la valutazione (ricorsione looping?)".

la prego di aiutarmi a individuare la chiamata non ricorsiva in coda in questo codice? Ho cercato parecchio, senza trovarlo. Cout è il let binding nella funzione sort?

Answer 1

L'espressione

merge (sort left) (sort right) 

non è ricorsiva in coda; chiama entrambi (ordinamento a sinistra) e (ordina a destra) in modo ricorsivo mentre rimane il lavoro nella chiamata (unione).

Penso che si possa risolvere il problema con un parametro aggiuntivo continuazione:

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 sort non è intrinsecamente ricorsiva in coda. Un ordinamento richiede due chiamate ricorsive e in qualsiasi esecuzione di qualsiasi funzione, al massimo una chiamata dinamica può essere in posizione di coda. (split viene anche chiamato dalla posizione non di coda, ma poiché dovrebbe utilizzare lo spazio di stack costante dovrebbe essere OK).

Assicurarsi che si sta utilizzando una versione recente di OCaml. Nelle versioni 3.08 e successive, List.rev potrebbe far esplodere lo stack. Questo problema è stato risolto nella versione 3.10. Utilizzando la versione 3.10.2, posso ordinare un elenco di dieci milioni di elementi usando il tuo codice. Ci vogliono un paio di minuti, ma non faccio saltare la pila. Quindi spero che il tuo problema sia semplicemente che hai una vecchia versione di OCaml.

In caso contrario, un buon passo successivo sarebbe quello di impostare la variabile d'ambiente

OCAMLRUNPARAM=b=1 

che darà una traccia dello stack quando si soffia lo stack.

Vorrei anche conoscere la lunghezza degli array che si sta cernita; sebbene merge sort non può essere ricorsiva in coda, la sua natura non-coda dovrebbe costare logaritmica spazio stack.

Se è necessario ordinare più di 10 milioni di elementi, forse si dovrebbe considerare un diverso algoritmo? Oppure, se lo si desidera, è possibile convertire manualmente il mergesort in CPS, che produrrà una versione ricorsiva della coda al costo di allocare le operazioni sull'heap. Ma la mia ipotesi è che non sarà necessario.