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

Question

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

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 для запуска данной функции несколько раз, каждый раз предоставляя ей последний вывод в качестве входных данных?Допустим, у меня есть строка, я хочу запустить функцию над строкой, затем снова запустить ее над результирующей строкой и так далее...

Answer 1

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

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

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

Компилятор 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

Answer 2

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