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

问题描述

在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，因为球拍智能地计算如下：（4 - （3 - （2 - （1-0）））），确实是2。

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

pre $ （define（flip bin-fn）
（lambda（xy）
（bin-fn yx）））


$ b $那么我们可以在Racket中实现与Haskell相同的行为：而不是（foldl - 0'（1 2 3 4）），我们可以这样写：（foldl（flip - ）0'（1 2 3 4））

问题是：为什么<$ c在以这种奇怪（非标准和非直觉）方式定义的球拍中，$ c> foldl ，dif不是任何其他语言？

解决方案

• Haskell定义不是均匀。在Racket中，这两个折叠的函数具有相同的输入顺序，因此您可以通过 foldr 替换 foldl 并得到相同的结果。如果你使用Haskell版本，你会得到一个不同的结果（通常） - 你可以在两种不同的类型中看到它。

  
  
  

  ，我认为为了做一个适当的比较，你应该避免这些玩具数字例子，其中两个类型变量都是整数。）




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

另一个区别是，Haskell版本是比常规方式更多地限制在Racket版本上：它仅在一个输入列表上操作，而Racket可以接受任意数量的列表。这使得为​​输入函数设定一个统一的参数顺序更为重要）。最后，假设Racket从许多其他功能中分离出来是错误的语言，因为折叠远不是一个新技巧，而且Racket的根源比Haskell（或其他语言）要古老得多。为什么Haskell的 foldl 以一种奇怪的方式定义？（不， （ - ）不是一个好借口。） 历史更新：



由于这似乎一次又一次地让人感到困扰，所以我做了一点运动。这在任何方面都不是确定性的，只是我的二手猜测。如果您知道更多，或者更好，请发送电子邮件给相关人员并提出要求，请随时编辑。具体来说，我不知道这些决定的制定日期，所以下面的列表是粗略的顺序。







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

  
  
  

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




• Lisp之后的第一个相关语言是ML。正如newacct在下面的回答中指出的那样，在那里做出的选择是与统一类型版本（即，Racket使用什么）。

下一个参考是Bird& Wadler的ItFP（1988），它使用不同类型（如在Haskell中）。然而，他们附录中的注意事项，米兰达具有相同类型（如在Racket中）。 ：//www.cs.kent.ac.uk/people/staff/dat/miranda/stdenv.htmlrel =noreferrer>切换参数顺序（即从Racket命令转移到Haskell一）。具体来说，该文本说：






警告 - foldl的这个定义与Miranda的旧版本不同。这里的一个和Bird和Wadler（1988）中的一样。旧的定义有两个'op'的参数被逆转。





• Haskell从Miranda那里拿了很多东西，包括不同种类。 （但是我当然不知道日期，所以Miranda的变化可能是由于Haskell造成的。）无论如何，现在很清楚，没有达成共识，因此上述相反的问题仍然存在。




• OCaml采用Haskell方向，并使用不同类型




• 我在猜测如何设计程序（又名HtDP）的写法大致相同期间，他们选择了同类型。然而，没有任何动机或解释 - 事实上，在练习之后，它简单地被称为其中一个内置函数。

  
  
  

  Racket的折叠操作当然，这里提到的是内置插件。

然后来到 SRFI-1 ，选择使用相同类型的版本（如Racket）。 John David Stone决定是一个问题，他指出注释：麻省理工学院计划和哈斯克尔翻转他们的的F的arg命令reduce c $ c>和 fold 函数。


Olin稍后解决了这个问题：他所说的只是：






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




他使用 state-value ，这表明一致的类型比操作符的顺序可能更重要一点。






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

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

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.

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

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

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

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

解决方案

• 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.)

• 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.

• 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).

• 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.)

Historical update:

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.

• 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.

  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.

• 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).

• 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 later on switched the argument order (ie, moved from the Racket order to the Haskell one). Specifically, that text says:

  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 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 went with the Haskell direction and uses different types

• 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's implementation of the fold operations was, of course, the "built-ins" that are mentioned here.

• 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

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

  Olin later addressed this: all he said was:

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

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

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