List.union

Hi Thomas,

It looks as a bug for me. Here is my corrected code (see working copy)
for method union in class List (I will also add a sentence to the Scala
comments saying that elements of "this" always occur before elements of
"that" in the result list) :

src/library/scala/List.scala (revision 17281)
====================================================
def union[B >: A](that: List[B]): List[B] = {
val b = new ListBuffer[B]
var these = this
while (!these.isEmpty) {
if (!that.contains(these.head)) b += these.head
these = these.tail
}
b.prependToList(that)
}

src/library/scala/List.scala (working copy)
====================================================
def union[B >: A](that: List[B]): List[B] = {
val these = this.removeDuplicates
val b = new ListBuffer[B] ++ these
var those = that
while (!those.isEmpty) {
if (!these.contains(those.head)) b += those.head
those = those.tail
}
b.toList
}

I suggest you add a ticket to Scala trac; I will check in the above
change to the SVN trunk (including addition of a test case !!) if nobody
objects.

Bye
--Stephane

Quoting Thomas Jung :

> Hi,
>
> I'm wondering if this behavior is a bug or as intended.
>
> Welcome to Scala version 2.7.3.final (Java HotSpot(TM) Client VM, Java
> 1.6.0_12)
>
> scala> val a = List("a", "a")
> a: List[java.lang.String] = List(a, a)
>
> scala> val b = List("a")
> b: List[java.lang.String] = List(a)
>
> scala> a.union(b)
> res0: List[java.lang.String] = List(a)
>
> scala> b.union(a)
> res1: List[java.lang.String] = List(a, a)
>
> Obviously union is not symmetric. Which is not very intuitive.
>
> The documentation for the return type says:
>
> > Returns a list without doubles containing the elements of this list
> and those of the given list that.
>
> But the result of b.union(a) has duplicates.
>
> The results seams to stem from the problem that the union operation can
> be naturally expressed for Set instances but not for List instances, or
> am I missing here something?
>
> Thomas
>
>
>
>

Hi Stephane,

the intersect method is not symetric, too.

val a = List("a")
val b = List("a", "a")

a intersect b
> List(a)
b intersect a
> List(a, a)
b intersect b
> List(a, a)

The documentation says nothing about duplicate entries, but if the are
removed for unions this will be true: (b intersect b) != (b union b). On
the other hand (b union b).length < b.length is not that natural. I
think there is no inconsistent solution to this problem. As long as
there are duplicates in the list there will be such inconsistencies.

Thomas

stephane.micheloud@epfl.ch schrieb:
> Hi Thomas,
>
> It looks as a bug for me. Here is my corrected code (see working copy)
> for method union in class List (I will also add a sentence to the Scala
> comments saying that elements of "this" always occur before elements of
> "that" in the result list) :
>
> src/library/scala/List.scala (revision 17281)
> ====================================================
> def union[B >: A](that: List[B]): List[B] = {
> val b = new ListBuffer[B]
> var these = this
> while (!these.isEmpty) {
> if (!that.contains(these.head)) b += these.head
> these = these.tail
> }
> b.prependToList(that)
> }
>
> src/library/scala/List.scala (working copy)
> ====================================================
> def union[B >: A](that: List[B]): List[B] = {
> val these = this.removeDuplicates
> val b = new ListBuffer[B] ++ these
> var those = that
> while (!those.isEmpty) {
> if (!these.contains(those.head)) b += those.head
> those = those.tail
> }
> b.toList
> }
>
> I suggest you add a ticket to Scala trac; I will check in the above
> change to the SVN trunk (including addition of a test case !!) if nobody
> objects.
>
> Bye
> --Stephane
>
>
> Quoting Thomas Jung :
>
>> Hi,
>>
>> I'm wondering if this behavior is a bug or as intended.
>>
>> Welcome to Scala version 2.7.3.final (Java HotSpot(TM) Client VM, Java
>> 1.6.0_12)
>>
>> scala> val a = List("a", "a")
>> a: List[java.lang.String] = List(a, a)
>>
>> scala> val b = List("a")
>> b: List[java.lang.String] = List(a)
>>
>> scala> a.union(b)
>> res0: List[java.lang.String] = List(a)
>>
>> scala> b.union(a)
>> res1: List[java.lang.String] = List(a, a)
>>
>> Obviously union is not symmetric. Which is not very intuitive.
>>
>> The documentation for the return type says:
>>
>> > Returns a list without doubles containing the elements of this list
>> and those of the given list that.
>>
>> But the result of b.union(a) has duplicates.
>>
>> The results seams to stem from the problem that the union operation can
>> be naturally expressed for Set instances but not for List instances, or
>> am I missing here something?
>>
>> Thomas
>>
>>
>>
>>
>
>
>

Hi Thomas,

You're right. In any case we need to update the Scala comments for
methods union and intersect in class List.
Changing the implementation to get symmetric methods will possibly
impact on user code. I'll ask Martin before checking in my changes.

Bye
--Stephane

Thomas Jung a écrit :
> Hi Stephane,
>
> the intersect method is not symetric, too.
>
> val a = List("a")
> val b = List("a", "a")
>
> a intersect b
> > List(a)
> b intersect a
> > List(a, a)
> b intersect b
> > List(a, a)
>
> The documentation says nothing about duplicate entries, but if the are
> removed for unions this will be true: (b intersect b) != (b union b). On
> the other hand (b union b).length < b.length is not that natural. I
> think there is no inconsistent solution to this problem. As long as
> there are duplicates in the list there will be such inconsistencies.
>
> Thomas
>
> stephane.micheloud@epfl.ch schrieb:
>
>> Hi Thomas,
>>
>> It looks as a bug for me. Here is my corrected code (see working copy)
>> for method union in class List (I will also add a sentence to the Scala
>> comments saying that elements of "this" always occur before elements of
>> "that" in the result list) :
>>
>> src/library/scala/List.scala (revision 17281)
>> ====================================================
>> def union[B >: A](that: List[B]): List[B] = {
>> val b = new ListBuffer[B]
>> var these = this
>> while (!these.isEmpty) {
>> if (!that.contains(these.head)) b += these.head
>> these = these.tail
>> }
>> b.prependToList(that)
>> }
>>
>> src/library/scala/List.scala (working copy)
>> ====================================================
>> def union[B >: A](that: List[B]): List[B] = {
>> val these = this.removeDuplicates
>> val b = new ListBuffer[B] ++ these
>> var those = that
>> while (!those.isEmpty) {
>> if (!these.contains(those.head)) b += those.head
>> those = those.tail
>> }
>> b.toList
>> }
>>
>> I suggest you add a ticket to Scala trac; I will check in the above
>> change to the SVN trunk (including addition of a test case !!) if nobody
>> objects.
>>
>> Bye
>> --Stephane
>>
>>
>> Quoting Thomas Jung :
>>
>>
>>> Hi,
>>>
>>> I'm wondering if this behavior is a bug or as intended.
>>>
>>> Welcome to Scala version 2.7.3.final (Java HotSpot(TM) Client VM, Java
>>> 1.6.0_12)
>>>
>>> scala> val a = List("a", "a")
>>> a: List[java.lang.String] = List(a, a)
>>>
>>> scala> val b = List("a")
>>> b: List[java.lang.String] = List(a)
>>>
>>> scala> a.union(b)
>>> res0: List[java.lang.String] = List(a)
>>>
>>> scala> b.union(a)
>>> res1: List[java.lang.String] = List(a, a)
>>>
>>> Obviously union is not symmetric. Which is not very intuitive.
>>>
>>> The documentation for the return type says:
>>>
>>> > Returns a list without doubles containing the elements of this list
>>> and those of the given list that.
>>>
>>> But the result of b.union(a) has duplicates.
>>>
>>> The results seams to stem from the problem that the union operation can
>>> be naturally expressed for Set instances but not for List instances, or
>>> am I missing here something?
>>>
>>> Thomas
>>>
>>>
>>>
>>>
>>>
>>
>>

I think union and intersection are broken as they are. I have no idea
what they should accomplish. It can't be set union/intersect, because
lists are not sets, they may contain duplicates. So the only possible
choice is multiset union/difference. But neither the current
implementation nor Stephane's correction does that. If they should be
multiset operations, then union is probably just ++ while intersect
has to be rewritten.
We can't hope that the operations will be symmetric as lists, but they
should be symmetric as multisets. That is,

a intersect b != b intersect a

yet they must contain the same elements, but possibly in different order.

I'd welcome a patch that does this.

Cheers

Hi again,

After reading again your comments (and looking at various user code) I
now also think the method union is not symmetric for lists AND we
should just update the Scala comment with a note (and may be an
example).

Bye
--Stephane

Le 11 mars 09 à 10:58, "stephane.micheloud@epfl.ch" a écrit :

> Hi Thomas,
>
> It looks as a bug for me. Here is my corrected code (see working copy)
> for method union in class List (I will also add a sentence to the
> Scala
> comments saying that elements of "this" always occur before elements
> of
> "that" in the result list) :
>
> src/library/scala/List.scala (revision 17281)
> ====================================================
> def union[B >: A](that: List[B]): List[B] = {
> val b = new ListBuffer[B]
> var these = this
> while (!these.isEmpty) {
> if (!that.contains(these.head)) b += these.head
> these = these.tail
> }
> b.prependToList(that)
> }
>
> src/library/scala/List.scala (working copy)
> ====================================================
> def union[B >: A](that: List[B]): List[B] = {
> val these = this.removeDuplicates
> val b = new ListBuffer[B] ++ these
> var those = that
> while (!those.isEmpty) {
> if (!these.contains(those.head)) b += those.head
> those = those.tail
> }
> b.toList
> }
>
> I suggest you add a ticket to Scala trac; I will check in the above
> change to the SVN trunk (including addition of a test case !!) if
> nobody
> objects.
>
> Bye
> --Stephane
>
>
> Quoting Thomas Jung :
>
>> Hi,
>>
>> I'm wondering if this behavior is a bug or as intended.
>>
>> Welcome to Scala version 2.7.3.final (Java HotSpot(TM) Client VM,
>> Java
>> 1.6.0_12)
>>
>> scala> val a = List("a", "a")
>> a: List[java.lang.String] = List(a, a)
>>
>> scala> val b = List("a")
>> b: List[java.lang.String] = List(a)
>>
>> scala> a.union(b)
>> res0: List[java.lang.String] = List(a)
>>
>> scala> b.union(a)
>> res1: List[java.lang.String] = List(a, a)
>>
>> Obviously union is not symmetric. Which is not very intuitive.
>>
>> The documentation for the return type says:
>>
>>> Returns a list without doubles containing the elements of this list
>> and those of the given list that.
>>
>> But the result of b.union(a) has duplicates.
>>
>> The results seams to stem from the problem that the union operation
>> can
>> be naturally expressed for Set instances but not for List
>> instances, or
>> am I missing here something?
>>
>> Thomas
>>
>>
>>
>>
>
>

Hi Martin,

I would like to provide a patch for the intersection method. But I was
not able to find out how to run one specs/scalacheck test (file) from ant.

(The build is not very convenient for windows users. It does not run
with the default java installation. One has to create a link to have a
JAVA_HOME path without whitespaces. The windows path length restriction
is annoying, too. Shouldn't it be possible to fork a process without a
command line > 255 characters? Well, both issues are minor problems but
could nonetheless discourage some developers.)

If lists should be interpreted as multisets with some notion of order
the behavior of list.intersect should be like described in the
specs/scalacheck test below.

"be symmetric after sorting" in {
forAll {
def sort(l: List[Int]) = l.sort( _ > _ )
(l1: List[Int], l2: List[Int]) => sort(l1 intersect l2) == sort(l2
intersect l1)
}
}

"obey min cardinality " in {

def cardinality(l : List[Int], e: Int) = (l filter(e == _)).size

forAll {
(l1: List[Int], l2: List[Int]) => {
val intersection = l1 intersect l2
l1.forall( e => cardinality(intersection, e) == (cardinality(l1, e)
min cardinality(l2,e)))
}
}
}

"maintain order" in {
forAll {
(l1: List[Int], l2: List[Int]) => {
val intersection = l1 intersect l2
val unconsumed = l1.foldLeft(intersection){(rest, e) =>
if(! rest.isEmpty && e == rest.head) rest.tail else rest
}
unconsumed.isEmpty
}
}
}

"has the list as again intersection" in {
forAll((l: List[Int]) => l == (l intersect l))
}

Thomas

martin odersky schrieb:
> I think union and intersection are broken as they are. I have no idea
> what they should accomplish. It can't be set union/intersect, because
> lists are not sets, they may contain duplicates. So the only possible
> choice is multiset union/difference. But neither the current
> implementation nor Stephane's correction does that. If they should be
> multiset operations, then union is probably just ++ while intersect
> has to be rewritten.
> We can't hope that the operations will be symmetric as lists, but they
> should be symmetric as multisets. That is,
>
> a intersect b != b intersect a
>
> yet they must contain the same elements, but possibly in different order.
>
> I'd welcome a patch that does this.
>
> Cheers
>

A Specification has a main, which is quite handy.

scala -classpath build/:lib/specs.jar:whatever com.you.YourSpec

should work.

2009/3/16 Thomas Jung :
> Hi Martin,
>
> I would like to provide a patch for the intersection method. But I was not
> able to find out how to run one specs/scalacheck test (file) from ant.
>
> (The build is not very convenient for windows users. It does not run with
> the default java installation. One has to create a link to have a JAVA_HOME
> path without whitespaces. The windows path length restriction is annoying,
> too. Shouldn't it be possible to fork a process without a command line > 255
> characters? Well, both issues are minor problems but could nonetheless
> discourage some developers.)
>
> If lists should be interpreted as multisets with some notion of order the
> behavior of list.intersect should be like described in the specs/scalacheck
> test below.
>
> "be symmetric after sorting" in {
>  forAll {
>        def sort(l: List[Int]) = l.sort( _ > _ )
>        (l1: List[Int], l2: List[Int]) => sort(l1 intersect l2) == sort(l2
> intersect l1)
>  }
> }
>
> "obey min cardinality " in {
>
>  def cardinality(l : List[Int], e: Int) = (l filter(e == _)).size
>
>  forAll {
>        (l1: List[Int], l2: List[Int]) => {
>                val intersection = l1 intersect l2
>                l1.forall( e => cardinality(intersection, e) ==
> (cardinality(l1, e) min cardinality(l2,e)))
>        }
>  }
> }
>
> "maintain order" in {
>  forAll {
>        (l1: List[Int], l2: List[Int]) => {
>                val intersection = l1 intersect l2
>                val unconsumed = l1.foldLeft(intersection){(rest, e) =>
>                  if(! rest.isEmpty && e == rest.head) rest.tail else rest
>                }
>                unconsumed.isEmpty
>          }
>  }
> }
>
> "has the list as again intersection" in {
>  forAll((l: List[Int]) => l == (l intersect l))
> }
>
> Thomas
>
> martin odersky schrieb:
>>
>> I think union and intersection are broken as they are. I have no idea
>> what they should accomplish. It can't be set union/intersect, because
>> lists are not sets, they may contain duplicates. So the only possible
>> choice is multiset union/difference. But neither the current
>> implementation nor Stephane's correction does that. If they should be
>> multiset operations, then union is probably just ++ while intersect
>> has to be rewritten.
>> We can't hope that the operations will be symmetric as lists, but they
>> should be symmetric as multisets. That is,
>>
>>  a intersect b   !=    b intersect a
>>
>> yet they must contain the same elements, but possibly in different order.
>>
>> I'd welcome a patch that does this.
>>
>> Cheers
>>
>>  -- Martin
>>
>

The command line issue was fixed in trunk a month or so ago, but I don't believe the ant/maven support has been updated to use it.  Granted, it's still only in trunk, but I for one think that the lazy maven-coordinator dude should get off his butt, and start using the new "short" command-line syntax!

-Josh
The lazy maven-coordinator dude



On Mon, Mar 16, 2009 at 5:32 AM, Thomas Jung <thomas.andreas.jung@googlemail.com> wrote:

Hi Martin,

I would like to provide a patch for the intersection method. But I was not able to find out how to run one specs/scalacheck test (file) from ant.

(The build is not very convenient for windows users. It does not run with the default java installation. One has to create a link to have a JAVA_HOME path without whitespaces. The windows path length restriction is annoying, too. Shouldn't it be possible to fork a process without a command line > 255 characters? Well, both issues are minor problems but could nonetheless discourage some developers.)

If lists should be interpreted as multisets with some notion of order the behavior of list.intersect should be like described in the specs/scalacheck test below.

"be symmetric after sorting" in {
 forAll {
       def sort(l: List[Int]) = l.sort( _ > _ )
       (l1: List[Int], l2: List[Int]) => sort(l1 intersect l2) == sort(l2 intersect l1)
 }
}

"obey min cardinality " in {

 def cardinality(l : List[Int], e: Int) = (l filter(e == _)).size

 forAll {
       (l1: List[Int], l2: List[Int]) => {
               val intersection = l1 intersect l2
               l1.forall( e => cardinality(intersection, e) == (cardinality(l1, e) min cardinality(l2,e)))
       }
 }
}

"maintain order" in {
 forAll {
       (l1: List[Int], l2: List[Int]) => {
               val intersection = l1 intersect l2
               val unconsumed = l1.foldLeft(intersection){(rest, e) =>
                 if(! rest.isEmpty && e == rest.head) rest.tail else rest
               }
               unconsumed.isEmpty
         }
 }
}

"has the list as again intersection" in {
 forAll((l: List[Int]) => l == (l intersect l))
}

Thomas

martin odersky schrieb:

I think union and intersection are broken as they are. I have no idea
what they should accomplish. It can't be set union/intersect, because
lists are not sets, they may contain duplicates. So the only possible
choice is multiset union/difference. But neither the current
implementation nor Stephane's correction does that. If they should be
multiset operations, then union is probably just ++ while intersect
has to be rewritten.
We can't hope that the operations will be symmetric as lists, but they
should be symmetric as multisets. That is,

 a intersect b   !=    b intersect a

yet they must contain the same elements, but possibly in different order.

I'd welcome a patch that does this.

Cheers

Hi Thomas,

I reimplemented the union/intersect/diff methods in class List as
multiset operations as Martin suggested.

The changes are available in SVN revision 17340:

https://lampsvn.epfl.ch/trac/scala/changeset/17340

I also added your test code to the test suite (file
test/files/run/lists.scala)

Concerning your two remarks about Windows, I suggest you to try the
following settings (I build Scala both on Windows and Unix for over 4
years :-) ):

1) Define the value of the JAVA_HOME variable as "c:\Progra~1\Scala"
(using the short Windows path name, see column 5 of "dir /x" command's
output !) instead of "c:\Program Files\Scala".

2) Define a virtual drive, eg. "subst x:
c:\localhome\michelou\projects\scala" in order to get around the Windows
console limitation on input line length ("input too long" error,
reported as "incorrect parameter" when running the scalafork Ant task).

Bye
--Stephane

Hi Stephane,

> I reimplemented the union/intersect/diff methods in class List as
> multiset operations as Martin suggested.
>
> The changes are available in SVN revision 17340:
>
> https://lampsvn.epfl.ch/trac/scala/changeset/17340

Nice.

It could be added to the documentation that the order of "this" list is
maintained.

> I also added your test code to the test suite (file
> test/files/run/lists.scala)

Is there a reason why you did not use the scalacheck test directly? I've
seen a dummy scalacheck test in the test suite but no "real" use. Using
scalacheck is quite natural for these kind of tests (as you could
hopefully see).

> Concerning your two remarks about Windows, I suggest you to try the
> following settings (I build Scala both on Windows and Unix for over 4
> years :-) ):
>
> 1) Define the value of the JAVA_HOME variable as "c:\Progra~1\Scala"
> (using the short Windows path name, see column 5 of "dir /x" command's
> output !) instead of "c:\Program Files\Scala".
>
> 2) Define a virtual drive, eg. "subst x:
> c:\localhome\michelou\projects\scala" in order to get around the Windows
> console limitation on input line length ("input too long" error,
> reported as "incorrect parameter" when running the scalafork Ant task).

I did use mklink. It works but it should be either be documented (maybe
it is but I could not find it) or be part of the build for windows.

Thomas