Почему в OCaml std lib так много нерекурсивных функций?

Question

Я переписывал многие стандартные библиотечные функции OCaml, чтобы в последнее время использовать хвостовую рекурсию. Учитывая, что это повлекло за собой прямое преобразование CPS, я не могу понять, почему версии по умолчанию не написаны таким образом.

Например, в стандартной библиотеке карта определяется как:

let rec map f = function
    []   -> []
  | a::l -> let r = f a in r :: map f l

Я переписал это, чтобы быть:

let map f l =
  let rec aux l k = match l with
      []   -> k []
    | a::l -> aux l (fun rest -> k (f a :: rest))
  in aux l (fun x -> x)

Answer 1

По моему опыту, хвостовые рекурсивные версии нетривиальных функций часто соотносят эффективность пространства с эффективностью времени. Другими словами, функции в стандартной библиотеке могут быть быстрее для небольших входных данных.

Answer 2

Ну, ваш код строит и передает "связанный список" замыканий (каждое из замыканий захватывает предыдущее как k) в куче вместо стека фреймов в стеке вызовов.

Более распространенный, эквивалентный способ сделать это хвостовой рекурсивностью состоит в том, чтобы пройти список результатов до сих пор (в обратном порядке, так как вы можете эффективно добавлять только вперед), а затем обратить его в конце:

let map f l =
  let rec aux l acc = match l with
      []   -> List.rev acc
    | a::l -> aux l (f a :: l)
  in aux l

(это в основном так же, как List.rev (List.rev_map f l))

В этом случае накапливается список результатов (в обратном порядке), а не закрытие. Но эффект точно такой же.

В обоих случаях нам нужно линейное пространство для некоторого промежуточного представления (кроме входного или выходного списка), поэтому с точки зрения сложности использования памяти нет преимущества перед нерекурсивно-рекурсивной версией. Хотя верно, что в куче больше памяти, чем в стеке, поэтому использование хвостовой рекурсивной версии, вероятно, будет работать для больших списков, чем не хвостовая рекурсивная версия. С точки зрения абсолютного использования памяти, опция накопления списка, вероятно, наиболее эффективна, потому что у замыканий и кадров стека больше накладных расходов.