Comment puis-je savoir si une fonction est récursive queue F #

J'ai écrit la fonction follwing:Comment puis-je savoir si une fonction est récursive queue F #

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 # a transformé en une boucle? Y at-il un moyen de le savoir sans utiliser Reflector (je n'ai aucune expérience avec Reflector et je ne sais pas C#)?

Éditer: Aussi, est-il possible d'écrire une fonction récursive de queue sans utiliser une fonction interne, ou est-il nécessaire pour la boucle de résider?

De même, existe-t-il une fonction dans F # std lib pour exécuter une fonction donnée un certain nombre de 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 l'exécuter à nouveau sur la chaîne résultante et ainsi de suite ...

Source

2009-04-30 Dave Berk

Voir aussi http://stackoverflow.com/questions/5809683/is-my-rec-function-tail-recursive – Brian

Malheureusement, il n'y a pas de manière triviale. Il n'est pas trop difficile de lire le code source et d'utiliser les types et de déterminer si quelque chose est un appel de queue par inspection (est-ce «la dernière chose», et pas dans un bloc «try»), mais les gens -se juger et faire des erreurs. Il n'y a pas de moyen automatisé simple (autre que par exemple l'inspection du code généré).

Bien sûr, vous pouvez simplement essayer votre fonction sur un gros morceau 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 queue (sauf si les drapeaux du compilateur pour les désactiver sont utilisés - utilisés pour quand vous voulez garder les cadres de pile pour le débogage), à l'exception de ceux directement récursifs. les fonctions seront optimisées en boucles. (EDIT: Je pense qu'aujourd'hui le compilateur F # n'émet pas de .tail dans les cas où il peut prouver qu'il n'y a pas de boucles récursives sur ce site d'appel, c'est une optimisation étant donné que l'opcode .tail est un peu plus lent sur beaucoup de plateformes). 'Tailcall' est un mot-clé réservé, avec l'idée qu'une future version de F # peut vous permettre d'écrire par exemple

tailcall func args

puis d'obtenir un avertissement/erreur si ce n'est pas un appel de fin. Seules les fonctions qui ne sont pas naturellement récursives à la queue (et qui ont donc besoin d'un paramètre d'accumulateur supplémentaire) vous «forceront» dans l'idiome de la «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

Source

2009-04-30 13:23:42 Brian

"tailcall" est intéressant, car il vous a spécifié le site d'appel au lieu de ce qui peut être un déclaration "tailrec" plus utile sur l'ensemble de la fonction. Pouvez-vous avoir une fonction "partiellement récursive"? –

@StephenSwensen Vous pouvez absolument. Les branches de flux de contrôle peuvent conduire à une alternative entre un appel de fin et un appel qui n'est pas un appel de fin, et vous pouvez seulement vouloir vérifier celui qui est réellement un appel de queue au moment de la compilation. 'let rec f x = si x> 0 alors f (1 + x) sinon 0 + f (1 + x)' illustre le concept, bien qu'il ne soit évidemment pas terminé. –

J'aime la règle générale Paul Graham formule en sur Lisp: s'il y a travail à faire, par exemple en manipulant la sortie d'appel récursif, l'appel n'est pas récursif en queue.

Source

2012-04-17 11:48:44 vemv

Comment puis-je savoir si une fonction est récursive queue F #

Répondre

Questions connexes