Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

ListSet.filter scrambles order of insertion #8985

Closed
scabug opened this issue Nov 16, 2014 · 8 comments
Closed

ListSet.filter scrambles order of insertion #8985

scabug opened this issue Nov 16, 2014 · 8 comments
Assignees
Milestone

Comments

@scabug
Copy link

scabug commented Nov 16, 2014

run following code will reverse the order of "_" and "model" in the ListSet:

val set = ListSet("", "model", "temp").filter( != "temp")

this will yield an ordered set in which "" precedes "model", different from ListSet("","model")

@scabug
Copy link
Author

scabug commented Nov 16, 2014

Imported From: https://issues.scala-lang.org/browse/SI-8985?orig=1
Reporter: Peng Cheng (peng)
Affected Versions: 2.10.4

@scabug
Copy link
Author

scabug commented Nov 17, 2014

@som-snytt said:
ListSet doesn't seem to make any promises about preserving iteration order.

Most operations reverse when building a new collection, but bulk add re-reverses the receiver.

scala> ListSet('a' to 'z': _*)
res7: scala.collection.immutable.ListSet[Char] = ListSet(z, y, x, w, v, u, t, s, r, q, p, o, n, m, l, k, j, i, h, g, f, e, d, c, b, a)

scala> ListSet('a' to 'z': _*).filter(_ != 'm')
res9: scala.collection.immutable.ListSet[Char] = ListSet(a, b, c, d, e, f, g, h, i, j, k, l, n, o, p, q, r, s, t, u, v, w, x, y, z)

scala> res9 ++ ('1' to '9')
res10: scala.collection.immutable.ListSet[Char] = ListSet(9, 8, 7, 6, 5, 4, 3, 2, 1, a, b, c, d, e, f, g, h, i, j, k, l, n, o, p, q, r, s, t, u, v, w, x, y, z)

@scabug
Copy link
Author

scabug commented Nov 19, 2014

Peng Cheng (peng) said:
exactly, while ListSet.filter is directly inherited from TraversableLike, which says:

/** Selects all elements of this $coll which satisfy a predicate.
*

  • @param p the predicate used to test elements.
  • @return a new $coll consisting of all elements of this $coll that satisfy the given
  •           predicate `p`. *The order of the elements is preserved.*
    

@scabug
Copy link
Author

scabug commented Nov 19, 2014

@som-snytt said:
I think the clause about preserving order applies if the collection is ordered.

"A traversable class might or might not have two properties: strictness and orderedness. Neither is represented as a type." That is, you can't tell by looking whether it is ordered.

A Seq is ordered because the docs say so. Since a ListSet isn't actually ListLike, maybe ListSet should be ListiveSet.

@scabug
Copy link
Author

scabug commented Dec 10, 2014

Peng Cheng (peng) said:
I personally think 'ListiveSet' is a redundant name unless implementing orderedness compromises many other features and performance. However I think the source code suggested that this is not the case

@scabug
Copy link
Author

scabug commented Jan 19, 2016

@SethTisue said (edited on Jan 19, 2016 10:08:31 PM UTC):
verified this is still present in 2.11.7 and 2.12.0-M3:

Welcome to Scala version 2.11.7 (Java HotSpot(TM) 64-Bit Server VM, Java 1.8.0_66).

scala> import scala.collection.immutable.ListSet
import scala.collection.immutable.ListSet

scala> ListSet('a' to 'z': _*)
res1: scala.collection.immutable.ListSet[Char] = ListSet(z, y, x, w, v, u, t, s, r, q, p, o, n, m, l, k, j, i, h, g, f, e, d, c, b, a)

scala> res1.filter(_ => true)
res2: scala.collection.immutable.ListSet[Char] = ListSet(a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z)

@scabug
Copy link
Author

scabug commented Jan 19, 2016

@SethTisue said:
This behavior seems a little less perverse if you consider that List has cheap prepend but expensive append.

At minimum, the documentation ought to be a lot better.

I think this is a little-used collection, so I've provisionally changed the milestone to Backlog.

@scabug
Copy link
Author

scabug commented May 17, 2016

@lrytz said:
fixed in scala/scala#5103

@scabug scabug closed this as completed May 17, 2016
@scabug scabug added this to the 2.12.0-M5 milestone Apr 7, 2017
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants