Как узнать, является ли функция хвостовой рекурсивной в F # - PullRequest
Новая
       53

Как узнать, является ли функция хвостовой рекурсивной в F #

15 голосов
/ 30 апреля 2009

Я написал следующую функцию: 

let str2lst str =
    let rec f s acc =
      match s with
        | "" -> acc
        | _  -> f (s.Substring 1) (s.[0]::acc)
    f str []

Как я могу узнать, что компилятор F # превратил его в цикл? Есть ли способ узнать без использования Reflector (у меня нет опыта работы с Reflector, и я не знаю C #)?

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

Кроме того, есть ли функция в F # std lib для запуска данной функции несколько раз, каждый раз давая ей последний вывод в качестве ввода? Допустим, у меня есть строка, я хочу запустить функцию над строкой, затем снова запустить ее над результирующей строкой и так далее ...

Ответы [ 2 ]

22 голосов
/ 30 апреля 2009

К сожалению, нет тривиального пути.

Нетрудно прочитать исходный код, использовать типы и определить, является ли что-то хвостовым вызовом путем проверки (это «последнее», а не в блоке «try»), но люди вторые. угадай себя и совершай ошибки. Нет простого автоматизированного способа (кроме, например, проверки сгенерированного кода).

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

Компилятор F # будет генерировать инструкции .tail IL для всех хвостовых вызовов (если только не используются флаги компилятора для их отключения - используется, когда вы хотите сохранить стековые фреймы для отладки), за исключением того, что непосредственно хвостовые рекурсивные функции будет оптимизирован в циклы. (РЕДАКТИРОВАТЬ: я думаю, что в настоящее время компилятор F # также не может генерировать .tail в тех случаях, когда он может доказать, что на этом сайте вызовов нет рекурсивных циклов; это оптимизация, учитывая, что код операции .tail немного медленнее на многих платформах.)

'tailcall' является зарезервированным ключевым словом, с мыслью, что будущая версия F # может позволить вам написать, например, 

tailcall func args

, а затем получите предупреждение / ошибку, если это не хвостовой вызов.

Только функции, которые не являются хвостовыми рекурсивами (и, следовательно, нуждаются в дополнительном параметре аккумулятора), «заставят» вас использовать идиому «внутренней функции».

Вот пример кода того, что вы спросили: 

let rec nTimes n f x =
    if n = 0 then
        x
    else
        nTimes (n-1) f (f x)

let r = nTimes 3 (fun s -> s ^ " is a rose") "A rose"
printfn "%s" r
2 голосов
/ 17 апреля 2012

Мне нравится эмпирическое правило, которое Пол Грэм формулирует в На Лиспе : если осталось работы, которую нужно выполнить , например. манипулируя выходом рекурсивного вызова, тогда вызов не является хвостовым рекурсивом.

...