48

在 Haskell 中，就像在许多其他函数式语言中一样，函数foldl被定义为，例如，foldl (-) 0 [1,2,3,4] = -10.

这没关系，因为foldl (-) 0 [1, 2,3,4]根据定义，((((0 - 1) - 2) - 3) - 4).

但是，在 Racket 中，(foldl - 0 '(1 2 3 4))是 2，因为 Racket “智能地”计算如下：(4 - (3 - (2 - (1 - 0))))，这确实是 2。

当然，如果我们定义辅助函数flip，像这样：

(define (flip bin-fn)
  (lambda (x y)
    (bin-fn y x)))

那么我们可以在 Racket 中实现与在 Haskell 中相同的行为：而不是(foldl - 0 '(1 2 3 4))我们可以编写：(foldl (flip -) 0 '(1 2 3 4))

问题是：为什么foldl在球拍中以如此奇怪（非标准和非直观）的方式定义，与任何其他语言不同？

4

4 回答 4

68

  • Haskell 的定义并不统一。在 Racket 中，两个折叠的函数具有相同的输入顺序，因此您可以替换foldl为foldr并获得相同的结果。如果您使用 Haskell 版本执行此操作（通常），您会得到不同的结果——您可以在两者的不同类型中看到这一点。

    （事实上​​，我认为为了进行适当的比较，您应该避免这些类型变量都是整数的玩具数字示例。）

  • 这有一个很好的副产品，鼓励您根据它们的语义差异进行foldl选择。foldr我的猜测是，使用 Haskell 的命令，您可能会根据操作进行选择。你有一个很好的例子：你使用foldl是因为你想减去每个数字 - 这是一个如此“明显”的选择，很容易忽略一个事实，这foldl通常是惰性语言中的一个糟糕选择。

  • 另一个区别是 Haskell 版本比 Racket 版本在通常的方式上受到更多限制：它只对一个输入列表进行操作，而 Racket 可以接受任意数量的列表。这使得输入函数具有统一的参数顺序变得更加重要）。

  • 最后，假设 Racket 与“许多其他函数式语言”不同是错误的，因为折叠远不是一个新技巧，而且 Racket 的根源比 Haskell（或这些其他语言）要古老得多。因此，问题可能会转向另一种方式：为什么foldl以一种奇怪的方式定义 Haskell？ （不，(-)这不是一个好的借口。）

历史更新：

由于这似乎一次又一次地困扰着人们，所以我做了一些跑腿工作。这不是绝对的，只是我的二手猜测。如果您了解更多，甚至更好，请随时编辑此内容，向相关人员发送电子邮件并询问。具体来说，我不知道做出这些决定的日期，所以下面的列表是粗略的。

  • 首先是 Lisp，没有提到任何形式的“折叠”。相反，Lisp 具有reduce非常不统一的特性，尤其是考虑到它的类型时。例如，:from-end是一个关键字参数，它确定它是左扫描还是右扫描，它使用不同的累加器函数，这意味着累加器类型取决于该关键字。这是对其他技巧的补充：通常第一个值是从列表中获取的（除非您指定一个:initial-value）。最后，如果您不指定:initial-value，并且列表为空，它实际上会将函数应用于零参数以获得结果。

    所有这一切意味着reduce通常用于顾名思义：将值列表减少为单个值，其中两种类型通常相同。这里的结论是，它的用途与折叠类似，但它不如通过折叠获得的通用列表迭代构造有用。我猜这意味着reduce和后来的折叠操作之间没有很强的关系。

  • 遵循 Lisp 并具有适当折叠的第一个相关语言是 ML。正如下面 newacct 的回答所指出的那样，在那里做出的选择是使用统一类型版本（即 Racket 使用的）。

  • 下一个参考是 Bird & Wadler 的 ItFP (1988)，它使用不同的类型（如在 Haskell 中）。但是，他们在附录中指出 Miranda 具有相同的类型（与 Racket 中的类型相同）。

  • Miranda 后来切换了参数顺序（即，从 Racket 顺序转移到 Haskell 顺序）。具体来说，该文本说：

    警告 - foldl 的定义与旧版本的 Miranda 不同。这里的一个与 Bird and Wadler (1988) 中的相同。旧定义将“op”的两个参数颠倒了。

  • Haskell 从 Miranda 那里拿走了很多东西，包括不同的类型。（但当然我不知道日期，所以米兰达的变化可能是由于 Haskell 造成的。）无论如何，在这一点上很明显没有达成共识，因此上述相反的问题成立。

  • OCaml 遵循 Haskell 方向并使用不同的类型

  • 我猜“如何设计程序”（又名 HtDP）是在大致同一时期编写的，他们选择了相同的类型。然而，没有动机或解释——事实上，在练习之后，它只是作为内置函数之一被提及。

    Racket 对折叠操作的实现当然是这里提到的“内置”。

  • 然后是SRFI-1，选择使用相同类型的版本（如 Racket）。这个决定是John David Stone 提出的问题，他指出 SRFI 中的一条评论说

    注意：MIT Scheme 和 Haskell 翻转了 F 的 arg 顺序，它们的reduce和fold函数。

    奥林后来谈到了这一点：他所说的只是：

    好点，但我想要两个函数之间的一致性。state-value first: srfi-1, SML state-value last: Haskell

    特别注意他对state-value的使用，这表明一致类型可能比运算符顺序更重要。

于 2012-01-08T20:14:11.287 回答
9

“不同于任何其他语言”

作为一个反例，标准 ML（ML 是一种非常古老且有影响力的函数式语言）foldl也以这种方式工作： http: //www.standardml.org/Basis/list.html#SIG :LIST.foldl:VAL

于 2012-01-09T03:38:06.097 回答
8

Racket's foldl and foldr (and also SRFI-1's fold and fold-right) have the property that

(foldr cons null lst) = lst
(foldl cons null lst) = (reverse lst)

I speculate the argument order was chosen for that reason.

于 2012-01-08T18:08:38.757 回答
3

从球拍文档中，描述foldl：

(foldl proc init lst ...+) → any/c

提到了您的问题的两个兴趣点：

输入 lsts 从左到右遍历

和

foldl 在恒定空间中处理 lst

为了简单起见，我将推测它的实现可能是什么样的，使用一个列表：

(define (my-foldl proc init lst)
  (define (iter lst acc)
    (if (null? lst)
        acc
        (iter (cdr lst) (proc (car lst) acc))))
  (iter lst init))

如您所见，满足从左到右遍历和恒定空间的要求（注意 中的尾递归iter），但在描述中从未指定参数的顺序。proc因此，调用上述代码的结果将是：

(my-foldl - 0 '(1 2 3 4))
> 2

如果我们proc以这种方式指定参数的顺序：

(proc acc (car lst))

那么结果将是：

(my-foldl - 0 '(1 2 3 4))
> -10

我的观点是， for 的文档foldl不会对参数的评估顺序做出任何假设proc，它只需要保证使用恒定空间并且列表中的元素是从左到右评估的。

作为旁注，您可以通过简单地编写以下内容来获得表达式所需的评估顺序：

(- 0 1 2 3 4)
> -10
于 2012-01-08T16:18:19.993 回答