Tại sao OCaml List.fold_right không được triển khai như đệ quy đuôi?

Question

List.fold_right không tail-recursive là như được chỉ ra ở đây http://caml.inria.fr/pub/docs/manual-ocaml/libref/List.html

Câu hỏi của tôi là tại sao List.fold_right đã không thực hiện như tail-recursive?

Tôi nghĩ rằng nó không phải là khó để làm như vậy

let rev l = 
    let rec revr acc = function 
    | [] -> acc 
    | hd::tl -> revr (hd::acc) tl 
    in 
    revr [] l;; 

let fold_right f l b = 
    let rev_l = rev l 
    in 
    let rec folder_rr acc = function 
    | [] -> acc 
    | hd::tl -> folder_rr (f hd acc) tl 
    in 
    folder_rr b rev_l;; 

Tôi cũng tìm thấy trong thư viện, một số chức năng không phải là tail-recursive trong khi họ có thể được thực hiện như tail-recursive. Nhà sản xuất đưa ra quyết định như thế nào?

Answer 1

Thực hiện đệ qui đuôi này có thể áp dụng fold_right cho danh sách lớn hơn, nhưng với chi phí chậm hơn cho danh sách ngắn hơn khi bạn phải duyệt qua danh sách hai lần. Các nhà phát triển ban đầu đã đánh giá rằng cho phép các trường hợp sử dụng cực đoan cho danh sách (nếu bạn có hàng nghìn yếu tố, bạn nên lập kế hoạch cho cấu trúc dữ liệu hiệu quả hơn) với chi phí của cả hai mã xấu hơn và làm cho màn biểu diễn của mọi người tồi tệ hơn. .

Có rất nhiều cách khác nhau để có bản đồ đệ quy đuôi, fold_right v.v. Bạn sẽ tìm thấy chúng trong thư viện mở rộng thư viện chuẩn, Extlib đáng kính, và Pin và Lõi mới hơn. Các kỹ thuật triển khai thực hiện từ của bạn, với các thủ thuật sử dụng phiên bản không phù hợp một cách tối ưu cho hàng nghìn mục đầu tiên và sau đó chuyển sang phiên bản tailrec, để các thủ thuật không an toàn xấu để thực hiện một lần duyệt ngang với chi phí đột biến ô khuyết điểm (cũng làm giảm hiệu suất).

Answer 2

Câu hỏi này đã được hỏi trước, có lẽ nhiều lần. Bạn có thể đọc một số câu trả lời trước đây:

Why does the OCaml std lib have so many non-tail-recursive functions?

câu trả lời nhanh của tôi là thực hiện phi đuôi-đệ quy thường là nhanh hơn rất nhiều đối với trường hợp smallish. Những người triển khai rõ ràng nghĩ đây là một sự cân bằng tốt.