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

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

ocaml continuation-passing tail-recursion
person efrey    schedule 17.08.2012    source источник
comment
Является ли CPS-версия функций более эффективной, чем версии с хвостовой рекурсией?   -  person Gab    schedule 18.08.2012
comment
@Gab CPS-версия рекурсивной функции обязательно является хвостовой рекурсией.   -  person efrey    schedule 18.08.2012
comment
Функция map — это случай хвостовой рекурсии по модулю cons.   -  person sdcvvc    schedule 19.08.2012

Ответы (2)


arrow_upward
8
arrow_downward

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

person Jeffrey Scofield    schedule 17.08.2012
comment
Как осуществляется этот компромисс? Я полагаю, что стоимость помещения и извлечения кадров стека в рекурсивных функциях, которые не устраняют хвостовые вызовы, приведет к снижению эффективности как в пространстве, так и во времени. Разве это не так? - person Chuck; 18.08.2012
comment
Что ж, очень часто хвостовая рекурсивная версия функции списка строит результат в обратном порядке, а затем переворачивает его в конце. Для короткого ввода версия без хвостовой рекурсии позволяет избежать обращения. Обобщенная передача продолжения может создать множество замыканий (по крайней мере, я так думаю). - person Jeffrey Scofield; 18.08.2012

arrow_upward
8
arrow_downward

Что ж, ваш код строит и передает «связанный список» замыканий (каждое из замыканий захватывает предыдущее как 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))

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

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

person newacct    schedule 17.08.2012