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

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

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

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

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

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

Ответ 1

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

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

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

Компилятор F # будет генерировать команды .tail IL для всех хвостовых вызовов (если не использовать флаги компилятора для их отключения), которые используются для того, чтобы вы сохраняли фреймы стека для отладки), за исключением того, что прямые хвостовые рекурсивные функции будут оптимизированы в циклы. (EDIT: Я думаю, что в настоящее время компилятор 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

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