Warum wurde OCaml List.fold_right nicht als Tail-Recursive implementiert?

Question

List.fold_right ist nicht tail-recursive wie hier angegeben http://caml.inria.fr/pub/docs/manual-ocaml/libref/List.html

Meine Frage, warum List.fold_right nicht als tail-recursive umgesetzt wurde?

Ich denke, es ist nicht schwer zu tun, so

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

ich auch in der Bibliothek gefunden, eine Reihe von Funktionen sind nicht tail-recursive, während sie als tail-recursive umgesetzt werden können. Wie hat der Hersteller solche Entscheidungen getroffen?

Answer 1

Diese tail-rekursive Implementierung ermöglicht es, fold_right auf größere Listen anzuwenden, aber auf Kosten von langsamer für kürzere Listen, da Sie die Liste zweimal durchlaufen müssen. Die ursprünglichen Entwickler beurteilten, dass extreme Listen für Use Cases (wenn Sie Tausende von Elementen haben, sollten Sie ohnehin eine effizientere Datenstruktur planen) auf Kosten von hässlicheren Code und schlechteren Performances für alle anderen, keinen guten Kompromiss darstellen .

Es gibt viele verschiedene Möglichkeiten, tail-recursive map, fold_right usw. zu verwenden. Sie finden sie in der Bibliothek, die die Standardbibliothek erweitern, die ehrwürdige Extlib und die neueren Batterien und den Kern. Die Implementierungstechniken gehen von Ihrem, zu Tricks, die eine nicht-tailrec-Version optimistisch für die ersten tausend oder so von Einzelteilen verwenden, und dann zu einer tailrec-Version, zu hässlichen unsicheren Tricks, um eine einzelne Durchquerung auf Kosten der Konsummutation durchzuführen (die auch die Leistungen verringern).

Answer 2

Diese Frage wurde schon oft gestellt. Sie können einige vorherigen Antworten lesen Sie hier:

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

Meine schnelle Antwort ist, dass die nicht-tail-rekursive Implementierung ist viel schneller oft für kleinere Fälle. Die Implementierer dachten offensichtlich, dass dies ein guter Kompromiss wäre.