F # эффективность карри? - PullRequest
Новая
       31

F # эффективность карри?

9 голосов
/ 24 апреля 2010

У меня есть функция, которая выглядит следующим образом: 

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

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

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

Однако, когда я использую функцию, подобную вышеприведенной, производительность низкая, так как оценка тела функции, записанного в «isInSet», кажется отложенной до тех пор, пока не известны все параметры - в частности, инвариантные биты, такие как (Set.ofList setElems).Contains переоцениваются при каждом выполнении isHtmlPath.

Как лучше всего сохранить краткую, читаемую природу F #, в то же время получая более эффективное поведение, при котором конструкция множества предварительно оценивается.

Выше просто пример ; Я ищу общий подход, который позволяет мне не тратить время на детали реализации - , где это возможно Я бы хотел не отвлекаться на детали, такие как порядок выполнения реализации, поскольку это обычно не важно для меня и подрывает главный пункт продажи функционального программирования.

Ответы [ 4 ]

9 голосов
/ 24 апреля 2010

Пока F # не различает чистый и нечистый код, я сомневаюсь, что мы увидим оптимизацию такого рода. Однако вы можете сделать карри явным. 

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

isHtmlSet теперь будет вызывать isInSet только один раз, чтобы получить закрытие, одновременно выполняя ofList.

5 голосов
/ 24 апреля 2010

Ответ от Kha показывает, как оптимизировать код вручную, используя непосредственные замыкания. Если это частый шаблон, который вам нужно часто использовать, также возможно определить функцию более высокого порядка, которая создает эффективный код из двух функций - первой, которая предварительно обрабатывает некоторых аргументов. и второй, который выполняет фактическую обработку после получения оставшихся аргументов.

Код будет выглядеть так: 

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

Вопрос в том, более ли это элегантно ...

Другая (сумасшедшая) идея состоит в том, что вы можете использовать для этого выражения вычислений. Определение компоновщика вычислений, которое позволяет вам делать это, очень нестандартно (это не то, что люди обычно делают с ними, и это никак не связано с монадами или какой-либо другой теорией). Однако, должно быть возможно написать это: 

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

В вычислении curry вы можете использовать let!, чтобы обозначить, что вы хотите получить следующий аргумент функции (после вычисления предыдущего кода): 

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

Вот некоторые ресурсы с дополнительной информацией о выражениях вычислений:

5 голосов
/ 24 апреля 2010

@ Kha ответ на месте. F # не может переписать 

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

в 

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

, если только он не знает, что g не имеет никаких эффектов, а в .NET Framework сегодня обычно невозможно рассуждать о последствиях 99% всех выражений. Это означает, что программист по-прежнему несет ответственность за явное кодирование порядка оценки, как указано выше.

2 голосов
/ 24 апреля 2010

  1. Карри не болит. Карри иногда вводит замыкания также. Они обычно тоже эффективны. см. этот вопрос Я задавал ранее. Вы можете использовать inline для повышения производительности при необходимости.

  2. Однако проблема с производительностью в этом примере в основном связана с вашим кодом:

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

здесь вам нужно выполнить Set.ofList setElems даже если вы его карри. Это стоит O (n log n) времени. Вам нужно изменить тип setElems на F # Set, а не List сейчас. Кстати, для небольших наборов использование списков происходит быстрее, чем наборы даже для запросов.

...