Scala中的右结合方法有什么好处？

Question

我刚开始接触Scala，了解到方法可以被定义为右结合（与常见的命令式面向对象语言中的左结合相反）。

一开始，当我看到Scala中使用cons建立列表的示例代码时，我注意到每个示例都是将列表放在右侧：

println(1 :: List(2, 3, 4))
newList = 42 :: originalList

然而，即使我反复看到这个写法，我也没有多想，因为当时我不知道::是List的一个方法。我只是假设它是一个运算符（再次强调在Java中的意义），并且结合律并不重要。在示例代码中，List总是出现在右侧，这似乎只是巧合（我认为这是可能的“首选样式”）。

现在我明白了：必须以这种方式编写，因为::是右结合的。

我的问题是，定义右结合方法有什么意义？

这是为了美学原因，还是右结合性在某些情况下实际上比左结合性更有益？

从我的（初学者）角度来看，我真的看不出来。

1 :: myList

是否比任何一个更好？

myList :: 1

但那显然是一个如此琐碎的例子，我怀疑这不是一个公平的比较。

- Mike Spross

---

我在我的答案中包含了你的评论，并且提供了一些例子来说明它们。 - VonC

据我所知，这是为了让Lisp用户感到宾至如归，纯粹是为了允许::列表追加操作。 - skaffman

不，它不是。阅读答案。 - Daniel C. Sobral

Answer 1

简单来说，从右往左结合可以通过使程序员输入与程序实际执行一致来提高可读性。
因此，如果您键入'1 :: 2 :: 3'，则会返回List(1, 2, 3)，而不是以完全不同的顺序返回List。
这是因为'1 :: 2 :: 3 :: Nil'实际上是从右往左进行操作的。

List[Int].3.prepend(2).prepend(1)

scala> 1 :: 2 :: 3:: Nil
res0: List[Int] = List(1, 2, 3)

这个方法既更易读，又更高效（对于prepend来说是O(1)，而假设有一个append方法则为O(n)）。

• 更易读
• 更高效

---

（提醒，摘自书籍Programming in Scala）
如果一个方法使用操作符表示法，例如a * b，则该方法在左操作数上被调用，就像a.*(b)一样——除非方法名以冒号结尾。
如果方法名以冒号结尾，则该方法在右操作数上被调用。
因此，在1 :: twoThree中，::方法在twoThree上被调用，并传入1，就像这样：twoThree.::(1)。

对于List，它扮演附加操作的角色（该列表似乎附加在“1”之后形成'1 2 3'，实际上是将1插入到列表中）。
类List不提供真正的附加操作，因为附加到列表需要的时间随着列表大小的增长而线性增长，而使用::进行前置操作只需恒定的时间。
myList :: 1会尝试将myList的整个内容前置到“1”上，这比将1前置到myList中要长（如'1 :: myList'）

注意：无论运算符具有什么结合性，它的操作数始终从左到右进行评估。
因此，如果b是一个不仅仅是对不可变值的简单引用的表达式，则a ::: b更精确地被视为以下块：

{ val x = a; b.:::(x) }

在这个块中，a仍然在b之前被评估，然后将该评估的结果作为操作数传递给b的 ::: 方法。

---

为什么要区分左结合和右结合方法呢？这样可以保持通常的左结合操作外观（"1 :: myList"），同时实际上在右表达式上应用操作，因为：

- 这更有效率。 - 但是使用逆结合顺序（"1 :: myList" vs. "myList.prepend(1)"）更易读。

所以正如你所说，“语法糖”，据我所知。

请注意，在foldLeft的情况下，例如，他们可能有点过头了（等价于'/:'的右结合运算符）。

---

为了包含一些你的评论，稍作改动：

如果你认为'append'函数是左结合的，那么你会写'oneTwo append 3 append 4 append 5'。
然而，如果它要将3、4和5附加到oneTwo（根据写法），那么复杂度将是O(N)。
'::'也是如此，只不过是用于“prepend”。

这意味着'a :: b :: Nil'是为了'List[].b.prepend(a)'。

如果'::'是要进行prepend并且仍保持左结合性，则结果列表将会顺序颠倒。
你希望它返回List(1, 2, 3, 4, 5)，但实际上它会返回List(5, 4, 3, 1, 2)，这可能出乎程序员的意料。 这是因为你所做的事情将按左结合顺序执行。

(1,2).prepend(3).prepend(4).prepend(5) : (5,4,3,1,2)

因此，右结合使代码与返回值的实际顺序匹配。

- VonC

---

是的，我知道以冒号（:) 结尾的方法适用于右侧，并且我已经看过关于在 List 前加入新元素是 O(1) 而不是 O(N) 的解释。我的问题更多的是为什么要区分左结合和右结合的方法？我试图找出支持右结合方法设计的基本原理。我猜想这纯粹是为了简化语法，但我想知道是否有更多深入考虑此设计选择的思路而非代码外观。 - Mike Spross

好的。我觉得我理解你的意思了。如果“::”是左结合的，那么你就会写成“oneTwo :: 3 :: 4 :: 5”。然而，如果它将3、4和5附加到oneTwo上（根据它的书写方式可以推断），那么时间复杂度将为O(N)。但是，如果“::”在保持左结合的同时前置，则生成的列表顺序将会错误。你希望它返回List(1, 2, 3, 4, 5)，但它最终返回的是List(5, 4, 3, 1, 2)，这可能会让程序员感到意外。因此，右结合性使代码与实际返回值的顺序匹配。 - Mike Spross

VonC，您能否将简短的答案移到回复顶部？我认为这样做会像右结合运算符一样提高可读性。 :-) - Daniel C. Sobral

我无法忘记fold的快捷方式。无论如何，在Scalaz库中可以找到其他例子 -- 马丁试图避免让Scala成为一个操作符重载的语言，这里所指的操作符是指方法中具体的非单词元素，因此您在标准库中找不到太多示例。不过，我要提出使用“~:”来表示正则表达式。 :-) - Daniel C. Sobral

我想补充一下：List(a, b, c).::(i) 实际上创建了一个形式为 (i, rest) 的列表，其中 rest 指向 List(a, b, c)。这就是为什么前置操作是 O(1) 的原因。 - Phương Nguyễn

Answer 2

当您执行列表折叠操作时，右结合和左结合非常重要。例如：

def concat[T](xs: List[T], ys: List[T]): List[T] = (xs foldRight ys)(_::_)

这个功能完全正常。但是您无法使用foldLeft操作执行相同的操作。

def concat[T](xs: List[T], ys: List[T]): List[T] = (xs foldLeft ys)(_::_)

因为::是右关联的。

- CodePredator

Answer 3

什么是定义右结合方法的意义？

我认为定义右结合方法的目的是为了给某人扩展语言的机会，这也是操作符重载的一般性质。

操作符重载是一个有用的东西，所以Scala说：为什么不将其开放给任何符号组合呢？或者说，为什么要区分运算符和方法？现在，库实现者如何与内置类型（例如Int）交互？在C++中，她会在全局范围内使用friend函数。如果我们想让所有类型都实现运算符“::”呢？

右结合性提供了一种干净的方法来将“::”运算符添加到所有类型中。当然，从技术上讲，“::”运算符是List类型的一个方法。但是，对于内置的Int和所有其他类型来说，它也是一个虚构的运算符，至少如果你忽略末尾的“:: Nil”的话。

我认为这反映了Scala实现尽可能多的内容在库中，并使语言灵活支持它们的哲学。这为某人提供了一个机会，可以提出SuperList，它可以被称为：

1 :: 2 :: SuperNil

有点不幸的是，目前只将右结合性硬编码到末尾的冒号中，但我猜这使得它易于记忆。

- Eugene Yokota