Как узнать, является ли функция хвостовой рекурсивной в 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, и я не знаю C#)?

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

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

Источник

3 ответа

Решение

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

Нетрудно прочитать исходный код и использовать типы и определить, является ли что-то хвостовым вызовом путем проверки (это "последнее", а не в блоке "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
Источник

Компилятор может проверить это за вас, начиная с F# 8! Отметьте функцию знакомTailCallAttribute, и вы получите предупреждение, если предоставите реализацию, не являющуюся хвостовой рекурсией.

Например, этот код:

      [<TailCall>]
let rec fibNaive n =
    if n <= 1 then n
    else fibNaive (n - 1) + fibNaive (n - 2)

выдает два экземпляраWarning FS3569 : The member or function 'fibNaive' has the 'TailCallAttribute' attribute, but is not being used in a tail recursive way.(по одному для каждого рекурсивного вызова)

Хотя этот код не выдает предупреждений:

      [<TailCall>]
let fibFast n =
    let rec fibFast x y n =
        match n with
        | _ when n < 1 -> x
        | 1 -> y
        | _ -> fibFast y (x + y) (n - 1)
    fibFast 0 1 n

Для получения бонусных баллов было бы неплохо превратить это в ошибку, добавив<WarningsAsErrors>FS3569</WarningsAsErrors>в ваш fsproj.

Источник

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

Источник
Другие вопросы по тегам