为什么 foldl 在 Racket 中以一种奇怪的方式定义? [英] Why is foldl defined in a strange way in Racket?

问题描述

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

In Haskell, like in many other functional languages, the function foldl is defined such that, for example, foldl (-) 0 [1,2,3,4] = -10.

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

This is OK, because foldl (-) 0 [1, 2,3,4] is, by definition, ((((0 - 1) - 2) - 3) - 4).

但是，在 Racket 中，(foldl - 0 '(1 2 3 4)) 是 2，因为 Racket 智能地"计算如下: (4 - (3 - (2- (1 - 0)))) ，确实是 2.

But, in Racket, (foldl - 0 '(1 2 3 4)) is 2, because Racket "intelligently" calculates like this: (4 - (3 - (2 - (1 - 0)))), which indeed is 2.

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

Of course, if we define auxiliary function flip, like this:

(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))

then we could in Racket achieve the same behavior as in Haskell: instead of (foldl - 0 '(1 2 3 4)) we can write: (foldl (flip -) 0 '(1 2 3 4))

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

The question is: Why is foldl in racket defined in such an odd (nonstandard and nonintuitive) way, differently than in any other language?

推荐答案

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

  • The Haskell definition is not uniform. In Racket, the function to both folds have the same order of inputs, and therefore you can just replace foldl by foldr and get the same result. If you do that with the Haskell version you'd get a different result (usually) — and you can see this in the different types of the two.

    (实际上，我认为为了进行适当的比较，您应该避免使用这些两个类型变量都是整数的玩具数字示例.)

    (In fact, I think that in order to do a proper comparison you should avoid these toy numeric examples where both of the type variables are integers.)

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

    This has the nice byproduct where you're encouraged to choose either foldl or foldr according to their semantic differences. My guess is that with Haskell's order you're likely to choose according to the operation. You have a good example for this: you've used foldl because you want to subtract each number — and that's such an "obvious" choice that it's easy to overlook the fact that foldl is usually a bad choice in a lazy language.

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

    Another difference is that the Haskell version is more limited than the Racket version in the usual way: it operates on exactly one input list, whereas Racket can accept any number of lists. This makes it more important to have a uniform argument order for the input function).

    最后，假设 Racket 与许多其他函数式语言"不同是错误的，因为折叠远不是一个新技巧，而且 Racket 的根源远比 Haskell(或这些其他语言)古老得多.因此，问题可以反过来:为什么 Haskell 的 foldl 以一种奇怪的方式定义?(不，(-) 不是一个好的借口.)

    Finally, it is wrong to assume that Racket diverged from "many other functional languages", since folding is far from a new trick, and Racket has roots that are far older than Haskell (or these other languages). The question could therefore go the other way: why is Haskell's foldl defined in a strange way? (And no, (-) is not a good excuse.)

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

    Since this seems to bother people again and again, I did a little bit of legwork. This is not definitive in any way, just my second-hand guessing. Feel free to edit this if you know more, or even better, email the relevant people and ask. Specifically, I don't know the dates where these decisions were made, so the following list is in rough order.

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

    • First there was Lisp, and no mention of "fold"ing of any kind. Instead, Lisp has reduce which is very non-uniform, especially if you consider its type. For example, :from-end is a keyword argument that determines whether it's a left or a right scan and it uses different accumulator functions which means that the accumulator type depends on that keyword. This is in addition to other hacks: usually the first value is taken from the list (unless you specify an :initial-value). Finally, if you don't specify an :initial-value, and the list is empty, it will actually apply the function on zero arguments to get a result.

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

    All of this means that reduce is usually used for what its name suggests: reducing a list of values into a single value, where the two types are usually the same. The conclusion here is that it's serving a kind of a similar purpose to folding, but it's not nearly as useful as the generic list iteration construct that you get with folding. I'm guessing that this means that there's no strong relation between reduce and the later fold operations.

    第一个遵循 Lisp 并具有适当折叠的相关语言是 ML.正如下面 newacct 的回答所述，在那里做出的选择是使用 统一类型版本(即 Racket 使用的内容).

    The first relevant language that follows Lisp and has a proper fold is ML. The choice that was made there, as noted in newacct's answer below, was to go with the uniform types version (ie, what Racket uses).

    下一个参考是 Bird &Wadler 的 ItFP (1988)，它使用 不同类型(如在 Haskell 中).但是，他们 注意在附录中 Miranda 具有相同的类型(如在 Racket 中).

    The next reference is Bird & Wadler's ItFP (1988), which uses different types (as in Haskell). However, they note in the appendix that Miranda has the same type (as in Racket).

    Miranda 后来在 改变了论证顺序(即，从 Racket 顺序移动到 Haskell 顺序).具体来说，该文字说:

    Miranda later on switched the argument order (ie, moved from the Racket order to the Haskell one). Specifically, that text says:

    警告 - foldl 的这个定义与旧版 Miranda 中的定义不同.这里的一个与 Bird 和 Wadler (1988) 中的相同.旧定义将 `op' 的两个参数颠倒了.

    WARNING - this definition of foldl differs from that in older versions of Miranda. The one here is the same as that in Bird and Wadler (1988). The old definition had the two args of `op' reversed.

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

  • Haskell took a lot of stuff from Miranda, including the different types. (But of course I don't know the dates so maybe the Miranda change was due to Haskell.) In any case, it's clear at this point that there was no consensus, hence the reversed question above holds.

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

    OCaml went with the Haskell direction and uses different types

    我猜如何设计程序"(又名 HtDP)大约是在同一时期编写的，他们选择了 相同类型.然而，没有动机或解释——事实上，在那次练习之后，它被简单地称为 其中一个内置函数.

    I'm guessing that "How to Design Programs" (aka HtDP) was written at roughly the same period, and they chose the same type. There is, however, no motivation or explanation — and in fact, after that exercise it's simply mentioned as one of the built-in functions.

    Racket 对 折叠操作当然是这里提到的内置".

    Racket's implementation of the fold operations was, of course, the "built-ins" that are mentioned here.

    然后是 SRFI-1，以及选择是使用相同类型的版本(如 Racket).这个决定是约翰大卫斯通的问题，他指出SRFI 中的评论说

    Then came SRFI-1, and the choice was to use the same-type version (as Racket). This decision was question by John David Stone, who points at a comment in the SRFI that says

    注意:MIT Scheme 和 Haskell 为他们的 reduce 和 fold 函数翻转了 F 的 arg 顺序.

    Note: MIT Scheme and Haskell flip F's arg order for their reduce and fold functions.

    Olin 后来解决了这个问题:他只说:

    Olin later addressed this: all he said was:

    好点，但我希望两个函数之间保持一致.状态值优先:srfi-1，SML最后一个状态值:Haskell

    Good point, but I want consistency between the two functions. state-value first: srfi-1, SML state-value last: Haskell

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

    Note in particular his use of state-value, which suggests a view where consistent types are a possibly more important point than operator order.

    这篇关于为什么 foldl 在 Racket 中以一种奇怪的方式定义?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！