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”中编写的函数体的评估似乎被延迟，直到所有参数都被设置为止。已知 - 特别是，每次执行 isHtmlPath 时都会重新评估诸如 (Set.ofList setElems).Contains 之类的不变位。

如何才能最好地保持 F# 的简洁、可读性，同时仍然获得更有效的行为（其中预先评估集合构造）。

以上只是一个例子；我正在寻找一种通用方法，避免让我陷入实现细节的困境 - 尽可能 我希望避免被实现的执行顺序等细节分散注意力，因为这通常对我来说并不重要，并且这有点破坏了函数式编程的一个主要卖点。

Answer 1

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

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

isHtmlSet 现在将仅调用 isInSet 一次来获取闭包，同时执行 ofList。

Answer 2

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)

• 上面的示例使用翻译的一些细节在 F# 规范 (PDF)

Answer 3

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

Answer 4

1. 柯里化不会造成伤害。柯里化有时也会引入闭包。他们通常也很有效率。
   参考我之前问过的这个问题。如有必要，您可以使用内联来提高性能。

2. 但是，示例中的性能问题主要是由于您的代码造成的：

   标准化 p |> (Set.ofList setElems).Contains

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