Why is the + operator for List deprecated in Scala?

Why is the + operator for List deprec开发者_如何学Pythonated in Scala?

http://www.scala-lang.org/docu/files/api/scala/List.html#%2B%28B%29

Good question, so I looked it up in the book by Odersky et al. It says the following (hopefully it's not a copyright infringement to quote this here ;-)):

Why not append to lists?

Class Listdoes not offer an append operation because the time it takes to append to a list grows linearly with the size of the list, whereas prepending with :: takes constant time. Your options if you want to build a list by appending elements is to prepend them, then when you're done call reverse; or use a ListBuffer, a mutable list that does offer an append operation, and when you're done call toList.

As far as I understand FP, prepending to a list is much more common than appending, at least in pure functional languages. I can only assume that the designers of Scala added the + operator as a convenience for Java developers, who are used to appending using add(), and then had second thoughts about it.

It was deprecated in May 2008 in revision 15071, with the message:

Deprecate all of the problematic + methods, and removed those that never appeared in a release.

I expect this was to avoid ambiguity with StringAdd#+. Compare the difference between 2.7.6 an 2.8.0 Beta below:

Welcome to Scala version 2.7.6.final (Java HotSpot(TM) 64-Bit Server VM, Java 1.6.0_15).
Type in expressions to have them evaluated.
Type :help for more information.

scala> List(1) + 2
warning: there were deprecation warnings; re-run with -deprecation for details
res0: List[Int] = List(1, 2)

scala> List(1) + "2"
warning: there were deprecation warnings; re-run with -deprecation for details
res1: List[Any] = List(1, 2)

In 2.8, the method has been removed and you get:

Welcome to Scala version 2.8.0.Beta1-RC8 (Java HotSpot(TM) 64-Bit Server VM, Java 1.6.0_15).
Type in expressions to have them evaluated.
Type :help for more information.

scala> List(1) + 2
<console>:5: error: type mismatch;
 found   : Int(2)
 required: String
       List(1) + 2
                 ^

scala> List(1) + "2"
res1: java.lang.String = List(1)2

UPDATE

On the scala-user list, Martin Odersky notes:

To find out what's really bad about List#+, consider what you would expect the following to produce:

List(1, 2, 3) + " is the correct result"

?

oxbow_lakes adds - it took me a while to unpack this cryptic comment but I think the point is that it would violate the commutativity of types implied by the + operator. That is, the type of a + b should be the same as the type of b + a

UPDATE Martin Odersky's clarification:

What would you expect

List(1, 2, 3) + " is the correct result"

to produce? I would expect a string: "List(1, 2, 3) is the correct result".

With 2.7 style List.+, you get instead a List[Any], List(1, 2, 3, "is the correct result").

I classify that as a bad surprise. In summary, one should never have a + method on collections that are covariant in their element type. Sets and maps are non-variant, that's why they can have a + method. It's all rather delicate and messy. We'd be better off if we did not try to duplicate Java's + for String concatenation. But when Scala got designed the idea was to keep essentially all of Java's expression syntax, including String +. And it's too late to change that now.

It was not commutative and was particularly suboptimal on lists. Furthermore, behavior differs between mutable and immutable collections. On Scala 2.8, you have the following:

element +: sequence   // prepend
sequence :+ element   // append
sequenece ++ sequence // concatenate

The mutable/immutable thing is not quite solved. A bunch of methods were deprecated as a first step, but they can't be changed or outright removed without a deprecation period first.

If you follow this thread, you will see it is probably for performance issue.

Generally one should arrange List construction so as to not append. Scala's List is an immutable single linked list, so appending to the end of it is an O(n) operation.

ListA ::: ListB is right-associative, and runs in time proportional to the length of ListA 'a ::: b' is a /prepend/ operation, which runs in O(a.length) time