Dlaczego OCaml List.fold_right nie został zaimplementowany jako rekursywny?

Question

List.fold_right nie tail-recursive jest wskazane tutaj http://caml.inria.fr/pub/docs/manual-ocaml/libref/List.html

Moje pytanie jest dlaczego List.fold_right nie został wdrożony jako tail-recursive?

myślę, że to nie jest trudne do zrobienia, więc

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

Ja również znaleźć się w bibliotece, wiele funkcji nie tail-recursive są natomiast mogą być realizowane jako tail-recursive. W jaki sposób producent podejmował takie decyzje?

Answer 1

Ta rekursywna implementacja ogonowa pozwala na zastosowanie fold_right do większych list, ale kosztem wolniejszego dla krótszych list, ponieważ musisz dwukrotnie przejść przez tę listę. Oryginalni programiści ocenili, że zezwalanie na ekstremalne przypadki użycia list (jeśli masz tysiące elementów, i tak powinieneś planować bardziej wydajną strukturę danych) kosztem obrzydliwego kodu i pogorszenie wyników innych osób nie było dobrym kompromisem .

Istnieje wiele różnych sposobów, aby mieć mapę rekursywną typu tail, fold_right itd. Znajdziesz je w bibliotece rozszerzającej standardową bibliotekę, czcigodny Extlib i nowsze baterie i jądro. Techniki implementacji idą od twoich, do trików z optymistyczną, nieopowierzchniową wersją dla pierwszego tysiąca przedmiotów, a potem do wersji brzydkiej, do brzydkich, niebezpiecznych sztuczek, które wykonują pojedyncze przejście kosztem mutacji w komórkach konsolowych (co również zmniejsza wydajność).

Answer 2

To pytanie zostało zadane wcześniej, prawdopodobnie wiele razy. Możesz przeczytać kilka poprzednich odpowiedzi tutaj:

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

Moja odpowiedź jest taka, że ​​szybkie wdrożenie non-tail-rekurencyjne jest często dużo szybciej niewielkich przypadkach. Implementatorzy najwyraźniej uważali, że to dobry kompromis.