đuôi đệ quy trong OCaml

Question

Tôi đang cố gắng để thực hiện một chức năng danh sách-sắp xếp đuôi-đệ quy trong OCaml, và tôi đã đi lên với đoạn mã sau:

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

Tuy nhiên, có vẻ như nó không thực sự là đệ quy đuôi, kể từ khi tôi gặp phải một "tràn ngăn xếp trong quá trình đánh giá (lặp đệ quy?)" lỗi.

Bạn có thể vui lòng giúp tôi phát hiện cuộc gọi không đệ quy trong mã này không? Tôi đã tìm kiếm khá nhiều, không tìm thấy nó. Cout nó được cho phép ràng buộc trong các chức năng sort?

Answer 1

Khái niệm

merge (sort left) (sort right) 

không phải là đuôi-đệ quy; nó gọi cả hai (sắp xếp bên trái) và (sắp xếp bên phải) đệ quy trong khi vẫn còn công việc trong cuộc gọi (hợp nhất).

Tôi nghĩ bạn có thể sửa chữa nó với một tham số tiếp tục bổ sung:

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 vốn đã không đuôi-đệ quy. Một sắp xếp yêu cầu hai các cuộc gọi đệ quy và trong bất kỳ thực thi chức năng nào, tối đa một cuộc gọi động có thể ở vị trí đuôi. (split cũng được gọi từ vị trí không đuôi, nhưng vì nó nên sử dụng không gian ngăn xếp liên tục nên được OK).

Đảm bảo bạn đang sử dụng phiên bản OCaml gần đây. Trong các phiên bản 3.08 trở lên, List.rev có thể làm nổ tung ngăn xếp. Vấn đề này được sửa trong phiên bản 3.10. Sử dụng phiên bản 3.10.2, tôi có thể sắp xếp danh sách mười triệu yếu tố sử dụng mã của bạn. Nó mất một vài phút, nhưng tôi không thổi đống. Vì vậy, tôi hy vọng vấn đề của bạn chỉ đơn giản là bạn có một phiên bản cũ của OCaml.

Nếu không, một bước tiếp theo sẽ là tốt để thiết lập các biến môi trường

OCAMLRUNPARAM=b=1 

mà sẽ cung cấp một chồng dấu vết khi bạn thổi stack.

Tôi cũng muốn biết độ dài của mảng mà bạn sắp xếp; mặc dù sắp xếp hợp nhất không thể có đuôi đệ quy, nhưng tính chất không đuôi của nó sẽ khiến bạn mất không gian ngăn xếp lôgarit.

Nếu bạn cần sắp xếp hơn 10 triệu phần tử, có thể bạn nên xem xét một thuật toán khác? Hoặc nếu bạn muốn, bạn có thể CPS-chuyển đổi mergesort bằng tay, mà sẽ mang lại một phiên bản đuôi đệ quy với chi phí phân bổ contiuations trên heap. Nhưng tôi đoán là nó sẽ không cần thiết.