F # rendement efficace?

Question

J'ai une fonction qui se présente comme suit:

let isInSet setElems normalize p = 
     normalize p |> (Set.ofList setElems).Contains 

Cette fonction peut être utilisée pour vérifier rapidement si un élément fait partie sémantiquement d'un certain jeu; par exemple, pour vérifier si un chemin de fichier appartient à un fichier html:

let getLowerExtension p = (Path.GetExtension p).ToLowerInvariant() 
let isHtmlPath = isInSet [".htm"; ".html"; ".xhtml"] getLowerExtension 

Cependant, lorsque j'utilise une fonction telle que ce qui précède, la performance est médiocre puisque l'évaluation du corps de la fonction comme écrit dans « isInSet » semble être retardé jusqu'à ce que tous les paramètres soient connus - en particulier, des bits invariants tels que (Set.ofList setElems).Contains sont réévalués à chaque exécution de isHtmlPath. Comment puis-je maintenir au mieux le caractère succinct et lisible de F # tout en obtenant le comportement le plus efficace dans lequel la construction de l'ensemble est pré-évaluée.

Ce qui précède est juste un exemple; Je cherche une approche générale qui évite de m'enfermer dans les détails d'implémentation - si possible Je voudrais éviter d'être distrait par des détails tels que l'ordre d'exécution de la mise en œuvre puisque cela n'est généralement pas important pour moi et en quelque sorte sape un problème majeur point de vente de la programmation fonctionnelle.

Answer 1

La réponse de Kha montre comment optimiser le code manuellement en utilisant des fermetures directement. S'il s'agit d'un modèle fréquent que vous devez utiliser souvent, il est également possible de définir une fonction d'ordre supérieur qui construit le code efficace à partir de deux fonctions - la première de pré-traitement de certains arguments et une seconde qui fait le traitement réel une fois qu'il obtient les arguments restants.

Le code ressemblerait à ceci:

let preProcess finit frun preInput = 
    let preRes = finit preInput 
    fun input -> frun preRes input 

let f : string list -> ((string -> string) * string) -> bool = 
    preProcess 
    Set.ofList       // Pre-processing of the first argument 
    (fun elemsSet (normalize, p) ->  // Implements the actual work to be 
     normalize p |> elemsSet.Contains) // .. done once we get the last argument 

Il est une question de savoir si cela est plus élégant que ...

autre (fou) idée est que vous pouvez utiliser des expressions de calcul pour cela. La définition de constructeur de calcul qui vous permet de faire ceci est très non-standard (ce n'est pas quelque chose que les gens font habituellement avec eux et il n'est aucunement lié aux monades ou à toute autre théorie). Cependant, il devrait être possible d'écrire ceci:

type CurryBuilder() = 
    member x.Bind((), f:'a -> 'b) = f 
    member x.Return(a) = a 
let curry = new CurryBuilder() 

Dans le calcul curry, vous pouvez utiliser let! pour indiquer que vous voulez prendre le prochain argument de la fonction (après l'évaluation du code précédente):

let f : string list -> (string -> string) -> string -> bool = curry { 
    let! elems =() 
    let elemsSet = Set.ofList elems 
    printf "elements converted" 
    let! normalize =() 
    let! p =() 
    printf "calling" 
    return normalize p |> elemsSet.Contains } 

let ff = f [ "a"; "b"; "c" ] (fun s -> s.ToLower()) 
// Prints 'elements converted' here 
ff "C" 
ff "D" 
// Prints 'calling' two times 

Voici quelques ressources avec plus d'informations sur les expressions de calcul:

• La manière habituelle d'utiliser express de calcul ions est décrit dans le chapitre de l'échantillon gratuit de mon livre: Chapter 12: Sequence Expressions and Alternative Workflows (PDF)

• L'exemple ci-dessus utilise des spécificités de la traduction qui est en pleine detailes décrits dans the F# specification (PDF)

Answer 2

1. Faire des travaux ne fait pas de mal. Currying introduit parfois des fermetures. Ils sont généralement efficaces aussi. référez-vous à this question j'ai demandé avant. Vous pouvez utiliser en ligne pour augmenter les performances si nécessaire.

2. Cependant, votre problème de performance dans l'exemple est principalement dû à votre code:

   normalize p |> (Set.ofList setElems).Contains

ici vous devez effectuer Set.ofList setElems même vous curry il. Cela coûte O (n log n) temps. Vous devez changer le type de setElems en F # Set, pas List maintenant. Btw, pour un petit ensemble, l'utilisation de listes est plus rapide que les ensembles, même pour l'interrogation.

Answer 3

Tant que F # ne fait pas la différence entre le code pur et le code impur, je doute que nous verrons des optimisations de ce genre. Vous pouvez, cependant, rendre le curry explicite.

let isInSet setElems = 
    let set = Set.ofList setElems 
    fun normalize p -> normalize p |> set.Contains 

isHtmlSet va maintenant appeler isInSet une seule fois pour obtenir la fermeture, en même temps l'exécution ofList.

Answer 4

@ La réponse de Kha est sur place. F # ne peut pas réécrire

// effects of g only after both x and y are passed 
let f x y = 
    let xStuff = g x 
    h xStuff y 

dans

// effects of g once after x passed, returning new closure waiting on y 
let f x = 
    let xStuff = g x 
    fun y -> h xStuff y 

à moins qu'il ne sait que g n'a pas d'effet, et dans le .NET Framework aujourd'hui, il est généralement impossible de raisonner sur les effets de 99% de toutes les expressions. Ce qui signifie que le programmeur est toujours responsable du codage explicite de l'ordre d'évaluation comme ci-dessus.