f# - F# 柯里化效率？

Question

我有一个如下所示的函数：

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# 的简洁、易读的性质，同时仍然获得更有效的行为，其中集合构造被预先评估。

以上只是一个例子；我正在寻找一种通用方法，以避免让我陷入实施细节 -在可能的情况下，我想避免被实施的执行顺序等细节分心，因为这对我来说通常并不重要，并且有点破坏主要卖点函数式编程。

score 9 · Accepted Answer

只要 F# 不区分纯代码和不纯代码，我怀疑我们会看到这种优化。但是，您可以使柯里化显式化。

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

isHtmlSet现在将isInSet只调用一次来获得闭包，同时执行ofList.

score 5 · Accepted Answer

@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% 的所有表达式的效果。这意味着程序员仍然负责如上所述的显式编码评估顺序。

score 5 · Accepted Answer

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

这是一个问题，但这是否更优雅......

另一个（疯狂的）想法是您可以为此使用计算表达式。允许您执行此操作的计算构建器的定义非常不标准（这不是人们通常使用它们做的事情，并且与 monad 或任何其他理论没有任何关系）。但是，应该可以这样写：

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

以下是一些资源，其中包含有关计算表达式的更多信息：

我的书的免费示例章节描述了使用计算表达式的常用方法：第 12 章：序列表达式和替代工作流程(PDF)
The example above uses some specifics of the translation which is in full detailes described in the F# specification (PDF)

score 2 · Accepted Answer

咖喱没有伤害。柯里化有时也会引入闭包。它们通常也很有效。参考我之前问过的这个问题。如有必要，您可以使用内联来提高性能。
但是，您在示例中的性能问题主要是由于您的代码：

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

Set.ofList setElems在这里，即使你咖喱它，你也需要表演。它花费 O(n log n) 时间。您现在需要将类型更改setElems为 F# Set，而不是 List。顺便说一句，对于小集合，使用列表比集合更快，即使是查询也是如此。

f# - F# 柯里化效率？

4 回答 4

Related

Reference