代码之家 › 专栏 › 技术社区 › Eamon Nerbonne

货币效率?

currying functional-programming f#

Eamon Nerbonne · 技术社区 · 14 年前

我有一个函数,如下所示:

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 回复 | 直到 14 年前

Tomas Petricek 14 年前

答案来自哈演示如何通过直接使用闭包手动优化代码。如果这是一个经常需要使用的模式,那么也可以定义一个高阶函数,它从两个函数构造有效的代码——第一个函数 预处理 一些论点和第二个论点 实际处理 一旦它得到剩余的参数。

代码如下:

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

不过,这是否更优雅是个问题……

另一个(疯狂的)想法是您可以为此使用计算表达式。允许您这样做的计算生成器的定义是非常不标准的(它不是人们通常用它们做的事情,并且它与monads或任何其他理论都没有任何关系)。但是,应该可以这样写:

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

以下是有关计算表达式的更多信息的一些资源:

通常使用计算表达式的方法在我书的自由样本章节中描述: Chapter 12: Sequence Expressions and Alternative Workflows (PDF)
上面的示例使用了翻译的一些细节,这些细节在 the F# specification (PDF)

Sebastian Ullrich 14 年前

只要F不区分纯代码和不纯代码,我怀疑我们会看到这种优化。但是,您可以将当前的内容明确化。

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

isHtmlSet 现在就给我打电话 isInSet 只有一次获得关闭,同时执行 ofList 。

Brian 14 年前

@哈伊的回答是当场作出的。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框架中,通常不可能解释99%表达式的效果。这意味着程序员仍然要像上面那样明确地编码评估顺序。

Community CDub 7 年前

咖喱不疼。咖喱有时也会引入闭包。他们通常也很有效率。请参阅 this question 我以前问过。如果需要,可以使用内联来提高性能。
但是,示例中的性能问题主要是由代码引起的:

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

在这里你需要表演 Set.ofList setElems 即使是咖喱。它花费O(n)个登录时间。你需要改变 setElems 到F集合,而不是现在列出。顺便说一句,对于小的集合,使用列表甚至比集合查询更快。