F # currying efficiency?

Question

Tengo una función que se ve de la siguiente manera:

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

Esta función se puede utilizar para comprobar rápidamente si un elemento es parte de un conjunto semántico; por ejemplo, para comprobar si una ruta de archivo pertenece a un archivo html:

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

Sin embargo, cuando se utiliza una función como la anterior, el rendimiento es pobre ya que la evaluación del cuerpo de la función como está escrito en "isInSet" parece que ser retrasada hasta que se conozcan todos los parámetros -, en particular, bits, invariantes tales como (Set.ofList setElems).Contains se vuelven a evaluar cada ejecución de isHtmlPath.

¿Cómo se puede mantener mejor que la naturaleza succint F # 's, legible al mismo tiempo conseguir el comportamiento más eficiente en el que se preevaluated la construcción de decorados.

Lo anterior es sólo un ejemplo; Estoy en busca de un enfoque general que me evita el empantanamiento en los detalles de implementación - cuando sea posible me gustaría evitar ser distraído por detalles como el orden de ejecución de la aplicación ya que eso es por lo general no es importante para mí y tipo de socava uno de los principales punto de venta de la programación funcional.

Answer 1

La respuesta de Kha muestra cómo optimizar el código manualmente mediante el uso de cierres directamente. Si este es un patrón frecuente que necesita usar a menudo, también es posible definir una función de orden superior que construye el código eficiente a partir de dos funciones: la primera que hace preprocesamiento de algunos argumentos y una segunda que hace el procesamiento real una vez que obtiene los argumentos restantes.

El código se vería así:

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 

Es una cuestión de si esto es más elegante, aunque ...

Otro (loco) idea es que se puede utilizar expresiones de cálculo para ello. La definición de constructor de cómputo que le permite hacer esto es muy no estándar (no es algo que la gente suele hacer con ellos y no está relacionado de ninguna manera con las mónadas o cualquier otra teoría). Sin embargo, debería ser posible escribir esto:

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

En el curry cálculo, puede utilizar let! para indicar que desea dar el siguiente argumento de la función (después de evaluar el código precedente):

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 

Éstos son algunos de los recursos con más información acerca de las expresiones de cálculo:

• La forma habitual de utilizar el cálculo expreso iones se describe en el capítulo muestra gratuita de mi libro: Chapter 12: Sequence Expressions and Alternative Workflows (PDF)

• El ejemplo anterior utiliza algunas características específicas de la traducción que está en Detailes completos descritos en the F# specification (PDF)

Answer 2

1. Currying does not hurt. Currying a veces también presenta cierres. Por lo general, también son eficientes. refiérase a this question pregunté antes. Puede usar en línea para aumentar el rendimiento si es necesario.

2. Sin embargo, el problema de rendimiento en el ejemplo se debe principalmente a su código:

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

Aquí es necesario para llevar a cabo Set.ofList setElems incluso curry ella. Cuesta tiempo O (n log n). Debe cambiar el tipo de setElems a F # Establecer, no a la lista ahora. Por cierto, para un conjunto pequeño, el uso de listas es más rápido que los conjuntos, incluso para consultar.

Answer 3

Mientras F # no diferencia entre el código puro e impuro, dudo que veremos optimizaciones de ese tipo. Sin embargo, puede hacer explícito el currying.

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

isHtmlSet ahora llamarán isInSet una sola vez para obtener el cierre, al mismo tiempo, la ejecución de ofList.

Answer 4

@ respuesta de Kha es el clavo. F # no se puede reescribir

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

en

// 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 

a menos que se sabe que g tiene ningún efecto, y en la actualidad el .NET Framework, por lo general es imposible razonar acerca de los efectos de un 99% de todas las expresiones. Lo que significa que el programador sigue siendo responsable de codificar explícitamente el orden de evaluación como se indicó anteriormente.