优化 Curry 所需的 Point Free Style

Question

假设我们有一个像这样的（设计的）函数：

import Data.List (sort)

contrived :: Ord a => [a] -> [a] -> [a]
contrived a b = (sort a) ++ b

并且我们将其部分应用到其他地方，例如：

map (contrived [3,2,1]) [[4],[5],[6]]

从表面上看，这与预期的一样：

[[1,2,3,4],[1,2,3,5],[1,2,3,6]]

但是，如果我们将一些 trace 放入：

import Debug.Trace (trace)

contrived :: Ord a => [a] -> [a] -> [a]
contrived a b = (trace "sorted" $ sort a) ++ b
map (contrived $ trace "a value" [3,2,1]) [[4],[5],[6]]

我们看到传递给 contrived 的第一个列表只被评估一次，但它对 [4,5,6] 中的每个项目进行排序：

[sorted
a value
[1,2,3,4],sorted
[1,2,3,5],sorted
[1,2,3,6]]

现在，contrived 可以相当简单地转换为无点样式：

contrived :: Ord a => [a] -> [a] -> [a]
contrived a = (++) (sort a)

部分应用时：

map (contrived [3,2,1]) [4,5,6]

仍然像我们预期的那样工作：

[[1,2,3,4],[1,2,3,5],[1,2,3,6]]

但是如果我们再次添加 traces:

contrived :: Ord a => [a] -> [a] -> [a]
contrived a = (++) (trace "sorted" $ sort a)
map (contrived $ trace "a value" [3,2,1]) [[4],[5],[6]]

我们看到现在传递给 contrived 的第一个列表仅被评估 并排序 一次：

[sorted
a value
[1,2,3,4],[1,2,3,5],[1,2,3,6]]

为什么会这样？既然转换成 pointfree 风格是如此微不足道，为什么 GHC 不能推断出它只需要在 contrived 的第一个版本中对 a 排序一次？

注意： 我知道对于这个相当简单的示例，使用 pointfree 样式可能更可取。这是一个人为的例子，我已经简化了很多。当以 pointfree 风格表达时，我遇到问题的真正功能不太清楚（在我看来）：

realFunction a b = conditionOne && conditionTwo
  where conditionOne = map (something a) b
        conditionTwo = somethingElse a b

在 pointfree 风格中，这需要围绕 (&&):

编写一个丑陋的包装器 (both)

realFunction a = both conditionOne conditionTwo
  where conditionOne = map (something a)
        conditionTwo = somethingElse a
        both f g x = (f x) && (g x)

顺便说一句，我也不确定 both 包装器为何起作用； realFunction 的 pointfree 风格的行为类似于 contrived 的 pointfree 风格版本，因为部分应用程序只被评估一次（即如果 something 排序 a 它只会这样做一次）。看来，由于 both 不是 pointfree，Haskell 应该有与非 pointfree contrived.

相同的问题

Answer 1

如果我没理解错的话，你正在找这个：

contrived :: Ord a => [a] -> [a] -> [a]
contrived a = let a' = sort a in \b -> a' ++ b
                    -- or ... in (a' ++)

如果您希望排序只计算一次，则必须在 \b.

之前完成

你说得对，编译器可以对此进行优化。这被称为 "full laziness" 优化。

如果我没记错的话，GHC 并不总是这样做，因为在一般情况下，它并不总是真正的优化。考虑人为的例子

foo :: Int -> Int -> Int
foo x y = let a = [1..x] in length a + y

当传递两个参数时，上述代码以常量工作space：列表元素在生成时立即被垃圾回收。

当部分应用 x 时，foo x 的闭包只需要 O(1) 内存，因为列表尚未生成。代码如

let f = foo 1000 in f 10 + f 20  -- (*)

仍然运行不变space。

相反，如果我们写

foo :: Int -> Int -> Int
foo x = let a = [1..x] in (length a +)

然后 (*) 将不再运行常量 space。第一次调用 f 10 将分配一个 1000 长的列表，并将其保存在内存中以供第二次调用 f 20.

注意你的部分应用

... = (++) (sort a)

本质上是

... = let a' = sort a in \b -> a' ++ b

因为参数传递涉及绑定，如 let。因此，您的 sort a 的结果将保留在以后的所有调用中。

优化 Curry 所需的 Point Free Style

Point Free Style Required for Optimized Curry

haskell

ghc

currying

pointfree

partial-application