Comment savoir si une fonction est queue récursive en fa #

Question

J'ai écrit la fonction suivante:

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

Comment puis-je savoir si le compilateur F # l'a transformé en boucle? Existe-t-il un moyen de le savoir sans utiliser Reflector (je n'ai aucune expérience de Reflector et je ne sais pas C #)?

Éditer: Est-il également possible d'écrire une fonction récursive sans utiliser de fonction interne ou faut-il que la boucle réside dans?

De plus, existe-t-il une fonction dans F # std lib pour exécuter une fonction donnée plusieurs fois, en lui donnant à chaque fois la dernière sortie en entrée? Disons que j'ai une chaîne, je veux exécuter une fonction sur la chaîne puis la réexécuter sur la chaîne résultante et ainsi de suite ...

Answer 1

Malheureusement, il n'y a pas de moyen trivial.

Il n’est pas trop difficile de lire le code source, d’utiliser les types et de déterminer s’il s’agit d’un appel final effectué après inspection (s’agit-il de «la dernière chose», et non d’un bloc «try»), mais des se deviner et faire des erreurs. Il n'y a pas de moyen automatisé simple (autre que l'inspection du code généré).

Bien sûr, vous pouvez simplement essayer votre fonction sur un grand nombre de données de test et voir si elle explose ou non.

Le compilateur F # générera des instructions .tail IL pour tous les appels de fin (sauf si les drapeaux du compilateur pour les désactiver sont utilisés - utilisés pour conserver des cadres de pile pour le débogage), à ??l'exception des fonctions directement récursives. sera optimisé en boucles. (EDIT: Je pense qu’aujourd’hui, le compilateur F # ne parvient pas non plus à émettre .tail dans les cas où il peut prouver qu’il n’ya pas de boucles récursives via ce site d’appel; il s’agit là d’une optimisation étant donné que l’opcode .tail est un peu plus lent sur de nombreuses plates-formes.)

'tailcall' est un mot clé réservé, dans l’idée qu’une future version de F # pourrait vous permettre d’écrire, par exemple.

tailcall func args

puis obtenez un avertissement / une erreur s'il ne s'agit pas d'un appel final.

Seules les fonctions qui ne sont pas naturellement récursives (et qui nécessitent donc un paramètre d'accumulateur supplémentaire) vous "forceront" à entrer dans l'idiome "fonction interne".

Voici un exemple de code de ce que vous avez demandé:

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

J'aime la règle générale de Paul Graham dans On Lisp : s'il reste du travail à faire , par exemple. en manipulant la sortie de l’appel récursif, l’appel n’est pas récursif.