为什么在Racket中以一种奇怪的方式定义foldl？

在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。

当然，如果我们定义辅助function翻转，像这样：

 (define (flip bin-fn) (lambda (xy) (bin-fn yx))) 

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

问题是：为什么在这样一种奇怪的（非标准的和非直觉的）方式中，与其他语言不同的是，

Answer 1

• Haskell的定义不统一 。 在球拍中，这两个褶皱的function具有相同的input顺序，因此您可以用foldrreplacefoldl并获得相同的结果。 如果你使用Haskell版本，你会得到一个不同的结果（通常） – 你可以看到这两个不同的types。

  （事实上​​，我认为为了做一个适当的比较，你应该避免这些玩具数字例子，其中两个typesvariables都是整数。）

• 这有很好的副产品，鼓励您根据语义差异selectfoldl或foldr 。 我的猜测是，根据Haskell的顺序，您可能会根据操作进行select。 你有一个很好的例子：你已经使用了foldl因为你想减去每个数字 – 这是一个“明显的”select，很容易忽略foldl通常是一个懒惰的语言不好的select的事实。

• 另一个不同之处在于，Haskell版本比通常的Racket版本更为有限：它只在一个input列表上运行，而Racket可以接受任意数量的列表。 这使得input函数具有统一的参数顺序更为重要）。

• 最后，假设Racket与“许多其他function性语言”是分离的，因为折叠远非一种新的技巧，而Racket的根源比Haskell（或其他语言）要古老得多。 这个问题也可能是另一 回事 ： 为什么Haskell的foldl以一种奇怪的方式定义？ （不， (-)不是一个很好的借口。）

历史更新：

由于这似乎一次又一次地困扰人们，我做了一点运动。 这不是什么明确的，只是我的二手猜测。 如果你知道更多，或者更好的话，请随时编辑，通过电子邮件发送给相关人员并提问。 具体来说，我不知道这些决定的date，所以下面的列表是粗略的。

• 首先是Lisp，没有提到任何“折叠”。 相反，Lisp的reduce非常不均匀，特别是如果你考虑它的types。 例如， :from-end是一个关键字参数，用于确定是左侧扫描还是右侧扫描，并使用不同的累加器函数，这意味着累加器types取决于该关键字。 这是除了其他黑客之外：通常第一个值是从列表（除非你指定一个:initial-value ）。 最后，如果你没有指定:initial-value ，并且列表是空的，它实际上将应用零参数的函数来得到结果。

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

• Lisp之后的第一个相关语言是ML。 正如在newacct的回答中所指出的那样，在那里做出的select是采用统一types的版本 （即，Racket使用的）。

• 下一个参考是Bird＆Wadler的ItFP（1988），它使用不同的types （如在Haskell中）。 然而，他们在附录中注意到米兰达的types是一样的（如在球拍中）。

• 米兰达后来改变了论据的顺序 （即从球拍命令转移到了哈斯克尔命令）。 具体来说，那个文字说：

  警告 – foldl的这个定义与Miranda的旧版本不同。 这里的一个和Bird和Wadler（1988）的一样。 旧的定义有两个“op”的反转。

• Haskell从Miranda那里拿了很多东西，包括不同types的东西。 （但是我当然不知道date，所以也许米兰达的变化是由于Haskell造成的）。无论如何，很明显在这一点上没有共识，因此上面提到的问题是相反的。

• OCaml采用了Haskell的方向，使用不同的types

• 我猜测“如何devise程序”（又名HtDP）是在大致相同的时期编写的，他们select了相同的types 。 然而，没有任何动机或解释 – 事实上，在这个练习之后，它被简单地称为内置函数之一 。

  球拍执行折叠操作当然是这里提到的“内置”。

• 然后来到SRFI-1 ，并select使用相同types的版本（如球拍）。 这个决定是由约翰·戴维·斯通（John David Stone）提出的，他在SRFI的评论中指出

  注意：MIT Scheme和Haskell翻转F的缩进和fold函数的arg顺序。

  奥林后来这样说：他所说的只是：

  好点，但我希望两个函数的一致性。 状态值优先：srfi-1，SML状态值最后一个：Haskell

  特别要注意他对状态值的使用 ，这表明了一致的types比操作符的顺序更重要。

Answer 2

“与其他语言不同”

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

Answer 3

球拍的fold和fold-right （以及SRFI-1的 fold和fold-right ）具有这样的性质

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

我猜测这个论据的顺序是因为这个原因而select的。

Answer 4

从Racket 文档中 ， foldl的描述：

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

提到你的问题的两个兴趣点：

input列表从左到右遍历

和

foldl在恒定的空间中处理lsts

我会推测如何执行，可能看起来像一个简单的列表清单：

 (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的尾recursion），但是proc的参数的顺序从未在描述中被指定。 因此，调用上面的代码的结果是：

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

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

 (proc acc (car lst)) 

那么结果将是：

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

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

作为一个方面说明，你可以通过简单的写下你的expression来得到想要的评估顺序：

 (- 0 1 2 3 4) > -10