爲什麼不將OCaml List.fold_right作爲尾遞歸實現？

Question

List.fold_right不tail-recursive這裏表示http://caml.inria.fr/pub/docs/manual-ocaml/libref/List.html

我的問題是，爲什麼List.fold_right沒有爲tail-recursive執行？

我認爲這是不難做到

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

我在圖書館還發現，許多功能都沒有tail-recursive，而他們可以爲tail-recursive來實現。 製造商是如何做出這樣的決定的？

Answer 1

這個尾遞歸實現可以將fold_right應用於較大的列表，但代價是較短的列表變慢，因爲您必須遍歷列表兩次。最初的開發人員認爲允許列表中的極端用例（如果您有成千上萬的元素，那麼您應該計劃一個更高效的數據結構），代價是兩個較醜陋的代碼，並且使其他人的表現更糟糕並不是一個好的權衡。

有許多不同的方式可以獲得尾遞歸地圖，fold_right等。您可以在擴展標準庫，古老的Extlib以及較新的Batteries和Core的庫中找到它們。這些實現技術從你自己開始，到爲前1000個項目樂觀地使用非tailrec版本，然後切換到tailrec版本，以醜陋的不安全技巧爲代價進行單遍歷（以cons細胞變異爲代價）這也降低了表演）。

Answer 2

此問題之前已被問過，可能很多次。你可以在這裏看到一些以前的答案：

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

我快速的回答是，非尾遞歸的實現往往是快了很多關於短小的情況。實施者顯然認爲這是一個很好的折衷。