Пример рекурсивной функции хвоста F#
Я плохо знаком с F# и читал о рекурсивных функциях хвоста и надеялся, что кто-то мог дать мне две различных реализации функционального нечто - то, которое является рекурсивным хвостом и тот, который не является так, чтобы я мог лучше понять принцип.
4 ответа
Начните с простой задачи, например, с отображения элементов из 'a в 'b в списке. Мы хотим написать функцию, имеющую сигнатуру
val map: ('a -> 'b) -> 'a list -> 'b list
Where
map (fun x -> x * 2) [1;2;3;4;5] == [2;4;6;8;10]
Начнем с не хвостовой рекурсивной версии:
let rec map f = function
| [] -> []
| x::xs -> f x::map f xs
Это не хвостовая рекурсия, потому что функция все еще должна выполнить работу после рекурсивного вызова. ::: является синтаксическим сахаром для List.Cons(f x, map f xs).
Нерекурсивная природа функции могла бы быть более очевидной, если бы я переписал последнюю строку как | x::xs -> let temp = map f xs; f x::temp - очевидно, что она выполняет работу после рекурсивного вызова.
Используйте переменную accumulator, чтобы сделать его хвостовым рекурсивным:
let map f l =
let rec loop acc = function
| [] -> List.rev acc
| x::xs -> loop (f x::acc) xs
loop [] l
Здесь мы строим новый список в переменной acc. Поскольку список строится в обратном порядке, нам нужно развернуть выходной список перед тем, как отдать его пользователю.
Если вы хотите немного поразмыслить, вы можете использовать continuation passing, чтобы написать код более кратко:
let map f l =
let rec loop cont = function
| [] -> cont []
| x::xs -> loop ( fun acc -> cont (f x::acc) ) xs
loop id l
Поскольку вызов loop и cont - это последние функции, вызываемые без дополнительной работы, они являются хвостовыми рекурсивными.
Это работает, потому что продолжение cont захватывается новым продолжением, которое, в свою очередь, захватывается другим, в результате чего получается некая древовидная структура данных следующего вида:
(fun acc -> (f 1)::acc)
((fun acc -> (f 2)::acc)
((fun acc -> (f 3)::acc)
((fun acc -> (f 4)::acc)
((fun acc -> (f 5)::acc)
(id [])))))
которая строит список по порядку, не требуя от вас обратного хода.
Если уж на то пошло, начните писать функции без хвостовой рекурсии, их легче читать и работать с ними.
Если вам нужно перебрать большой список, используйте переменную-аккумулятор.
Если вы не можете найти удобный способ использования аккумулятора, а других вариантов в вашем распоряжении нет, используйте продолжения. Я лично считаю нетривиальное, интенсивное использование континуумов трудным для чтения.
Попытка более краткого объяснения, чем в других примерах:
let rec foo n =
match n with
| 0 -> 0
| _ -> 2 + foo (n-1)
let rec bar acc n =
match n with
| 0 -> acc
| _ -> bar (acc+2) (n-1)
foo не является хвостовой рекурсией, потому что foo должен вызывать foo рекурсивно, чтобы оценить "2+foo(n-1)" и вернуть его.
bar является хвостовой рекурсией, потому что bar не нужно использовать возвращаемое значение рекурсивного вызова, чтобы вернуть значение. Он может просто позволить рекурсивному вызову bar немедленно вернуть свое значение (без возврата на весь стек вызова). Компилятор видит это и "обманывает", переписывая рекурсию в цикл.
Замена последней строки в bar на "| _ -> 2+(bar (acc+2) (n-1))" уничтожит рекурсивность хвостовой части.
Вот более наглядный пример, сравните его с тем, что вы обычно делаете для факториала.
let factorial n =
let rec fact n acc =
match n with
| 0 -> acc
| _ -> fact (n-1) (acc*n)
fact n 1
Этот пример немного сложнее, но идея в том, что у вас есть аккумулятор, который ведет подсчет, а не изменяет возвращаемое значение.
Кроме того, такой стиль обертывания обычно является хорошей идеей, так как вызывающему вас пользователю не нужно беспокоиться о заполнении аккумулятора (обратите внимание, что факт является локальным для функции)
.Также при тестировании не забывайте, что косвенная хвостовая рекурсия (хвостовой вызов) отключена по умолчанию при компиляции в режиме отладки. Это может вызвать переполнение стека хвостовой рекурсией в режиме отладки, но не в режиме выпуска.