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

В последнее время я переписал многие стандартные библиотечные функции 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)

Ответ 1

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

Ответ 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))

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

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