Quantcast

In-place mutable operations

classic Classic list List threaded Threaded
19 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

In-place mutable operations

Rex Kerr-2
There are a bunch of collections methods that could be implemented as in-place operations on mutable versions of the collection, but currently are not.  Although I appreciate the peace of mind of using immutable collections, it is sometimes frustrating to have to implement a remap for the Nth time, and often I just end up using `Array` or something instead of a more convenient collection because I don't have access to all the methods necessary to make the mutable version fast.

So I propose that the collections methods ought to have a robust set of in-place operations, possibly notated by postfixing the method with InPlace (or some other better word--maybe the suffix -ize?).  These should include things like (for something both Shrinkable and Growable):

  collectInPlace(pf: PartialFunction[A, A])
  diffInPlace(xs: Seq[A])
  distinctInPlace
  dropInPlace(n: Int)
  dropRightInPlace(n: Int)
  dropWhileInPlace(f: A => Boolean)
  filterInPlace(f: A => Boolean)
  filterNotInPlace(f: A => Boolean)
  flatMapInPlace(f: A => Traversable[A])
  initInPlace
  intersectInPlace(xs: Seq[A])
  mapInPlace(f: A => A)
  reverseInPlace
  scanLeftInPlace(z: A)(f: (A,A) => A)
  scanRightInPlace(z: A)(f: (A,A) => A)
  tailInPlace
  unionInPlace(xs: Seq[A])

Without methods like these, the utility of the mutable collections is considerably curtailed, and also leads to mutable collections stored in mutable vars since it is so often easier to build a new mutable collection than to change the one that you've got to be what you need.

So, my questions are:
  (1) Is it agreed that something like this is a good idea?
  (2) Is it planned, and what is the timeframe?
  (3) How could one contribute to this happening sooner rather than later (if the desirability is agreed upon)?

--Rex
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: In-place mutable operations

Erik Engbrecht
I have been really, really wishing for these the past few days.  I think it's an excellent idea.

On Thu, Dec 23, 2010 at 5:46 PM, Rex Kerr <[hidden email]> wrote:
There are a bunch of collections methods that could be implemented as in-place operations on mutable versions of the collection, but currently are not.  Although I appreciate the peace of mind of using immutable collections, it is sometimes frustrating to have to implement a remap for the Nth time, and often I just end up using `Array` or something instead of a more convenient collection because I don't have access to all the methods necessary to make the mutable version fast.

So I propose that the collections methods ought to have a robust set of in-place operations, possibly notated by postfixing the method with InPlace (or some other better word--maybe the suffix -ize?).  These should include things like (for something both Shrinkable and Growable):

  collectInPlace(pf: PartialFunction[A, A])
  diffInPlace(xs: Seq[A])
  distinctInPlace
  dropInPlace(n: Int)
  dropRightInPlace(n: Int)
  dropWhileInPlace(f: A => Boolean)
  filterInPlace(f: A => Boolean)
  filterNotInPlace(f: A => Boolean)
  flatMapInPlace(f: A => Traversable[A])
  initInPlace
  intersectInPlace(xs: Seq[A])
  mapInPlace(f: A => A)
  reverseInPlace
  scanLeftInPlace(z: A)(f: (A,A) => A)
  scanRightInPlace(z: A)(f: (A,A) => A)
  tailInPlace
  unionInPlace(xs: Seq[A])

Without methods like these, the utility of the mutable collections is considerably curtailed, and also leads to mutable collections stored in mutable vars since it is so often easier to build a new mutable collection than to change the one that you've got to be what you need.

So, my questions are:
  (1) Is it agreed that something like this is a good idea?
  (2) Is it planned, and what is the timeframe?
  (3) How could one contribute to this happening sooner rather than later (if the desirability is agreed upon)?

--Rex

Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: In-place mutable operations

Jesper Nordenberg
In reply to this post by Rex Kerr-2
Any reason why you can't implement these as extension methods?

/Jesper Nordenberg

Rex Kerr skrev 2010-12-23 23:46:

> There are a bunch of collections methods that could be implemented as
> in-place operations on mutable versions of the collection, but currently
> are not.  Although I appreciate the peace of mind of using immutable
> collections, it is sometimes frustrating to have to implement a remap
> for the Nth time, and often I just end up using `Array` or something
> instead of a more convenient collection because I don't have access to
> all the methods necessary to make the mutable version fast.
>
> So I propose that the collections methods ought to have a robust set of
> in-place operations, possibly notated by postfixing the method with
> InPlace (or some other better word--maybe the suffix -ize?).  These
> should include things like (for something both Shrinkable and Growable):
>
>    collectInPlace(pf: PartialFunction[A, A])
>    diffInPlace(xs: Seq[A])
>    distinctInPlace
>    dropInPlace(n: Int)
>    dropRightInPlace(n: Int)
>    dropWhileInPlace(f: A => Boolean)
>    filterInPlace(f: A => Boolean)
>    filterNotInPlace(f: A => Boolean)
>    flatMapInPlace(f: A => Traversable[A])
>    initInPlace
>    intersectInPlace(xs: Seq[A])
>    mapInPlace(f: A => A)
>    reverseInPlace
>    scanLeftInPlace(z: A)(f: (A,A) => A)
>    scanRightInPlace(z: A)(f: (A,A) => A)
>    tailInPlace
>    unionInPlace(xs: Seq[A])
>
> Without methods like these, the utility of the mutable collections is
> considerably curtailed, and also leads to mutable collections stored in
> mutable vars since it is so often easier to build a new mutable
> collection than to change the one that you've got to be what you need.
>
> So, my questions are:
>    (1) Is it agreed that something like this is a good idea?
>    (2) Is it planned, and what is the timeframe?
>    (3) How could one contribute to this happening sooner rather than
> later (if the desirability is agreed upon)?
>
> --Rex


Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: In-place mutable operations

Jesper Nordenberg
In reply to this post by Rex Kerr-2
Any reason why you can't implement these as extension methods?

/Jesper Nordenberg

Rex Kerr skrev 2010-12-23 23:46:

> There are a bunch of collections methods that could be implemented as
> in-place operations on mutable versions of the collection, but currently
> are not.  Although I appreciate the peace of mind of using immutable
> collections, it is sometimes frustrating to have to implement a remap
> for the Nth time, and often I just end up using `Array` or something
> instead of a more convenient collection because I don't have access to
> all the methods necessary to make the mutable version fast.
>
> So I propose that the collections methods ought to have a robust set of
> in-place operations, possibly notated by postfixing the method with
> InPlace (or some other better word--maybe the suffix -ize?).  These
> should include things like (for something both Shrinkable and Growable):
>
>    collectInPlace(pf: PartialFunction[A, A])
>    diffInPlace(xs: Seq[A])
>    distinctInPlace
>    dropInPlace(n: Int)
>    dropRightInPlace(n: Int)
>    dropWhileInPlace(f: A => Boolean)
>    filterInPlace(f: A => Boolean)
>    filterNotInPlace(f: A => Boolean)
>    flatMapInPlace(f: A => Traversable[A])
>    initInPlace
>    intersectInPlace(xs: Seq[A])
>    mapInPlace(f: A => A)
>    reverseInPlace
>    scanLeftInPlace(z: A)(f: (A,A) => A)
>    scanRightInPlace(z: A)(f: (A,A) => A)
>    tailInPlace
>    unionInPlace(xs: Seq[A])
>
> Without methods like these, the utility of the mutable collections is
> considerably curtailed, and also leads to mutable collections stored in
> mutable vars since it is so often easier to build a new mutable
> collection than to change the one that you've got to be what you need.
>
> So, my questions are:
>    (1) Is it agreed that something like this is a good idea?
>    (2) Is it planned, and what is the timeframe?
>    (3) How could one contribute to this happening sooner rather than
> later (if the desirability is agreed upon)?
>
> --Rex


Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: In-place mutable operations

Seth Tisue
In reply to this post by Rex Kerr-2
>>>>> "Rex" == Rex Kerr <[hidden email]> writes:

 Rex> So I propose that the collections methods ought to have a robust
 Rex> set of in-place operations, possibly notated by postfixing the
 Rex> method with InPlace (or some other better word--maybe the suffix
 Rex> -ize?).  [...]

I like it, but I also worry about namespace clutter.  Perhaps a more
orthogonal design is possible.

How about an inPlace method on mutable collections that returns a kind
of view?  "View" isn't quite the right word, maybe.  Anyway, operations
on this "view" would have the usual names, but would actually alter the
original collection instead of constructing new ones.  So instead of:

  mySeq.filterInPlace(myPredicate)

you'd write:

  mySeq.inPlace.filter(myPredicate)

Methods on the view would return the same view again, so you could chain
operations:

  mySeq.inPlace.filter(myPredicate).map(myFunction)

--
Seth Tisue @ Northwestern University | http://tisue.net
lead developer, NetLogo: http://ccl.northwestern.edu/netlogo/
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: In-place mutable operations

Rex Kerr-2
On Thu, Dec 23, 2010 at 6:14 PM, Seth Tisue <[hidden email]> wrote:
>>>>> "Rex" == Rex Kerr <[hidden email]> writes:

 Rex> So I propose that the collections methods ought to have a robust
 Rex> set of in-place operations, possibly notated by postfixing the
 Rex> method with InPlace (or some other better word--maybe the suffix
 Rex> -ize?).  [...]

I like it, but I also worry about namespace clutter.  Perhaps a more
orthogonal design is possible.

How about an inPlace method on mutable collections that returns a kind
of view?  "View" isn't quite the right word, maybe.  Anyway, operations
on this "view" would have the usual names, but would actually alter the
original collection instead of constructing new ones.  So instead of:

 mySeq.filterInPlace(myPredicate)

you'd write:

 mySeq.inPlace.filter(myPredicate)

I have considered this, and I certainly prefer it syntactically.  (I've proposed that the same should be done for all the xOption methods that are inconsistently present and clutter the namespace.)

The problem with doing so here is that you unavoidably have an object creation each time you ask for it inPlace, and there's usually not much point using mutable collections if you're not interested in efficiency.  Almost everything is conceptually easier with immutable collections.

So I think I would want to test the performance each way (in the ideal high-performance case, i.e. with specialized primitives) before agreeing to one vs. the other.

  --Rex

Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: In-place mutable operations

Rex Kerr-2
In reply to this post by Jesper Nordenberg
Many of the desired operations can only happen efficiently if you have access to the innards of the collection.  For example, you need access to the array underlying the HashMap to get an efficient filter; otherwise, you have to seek on every removal.  So you couldn't do it with implicits.

  --Rex

On Thu, Dec 23, 2010 at 6:14 PM, Jesper Nordenberg <[hidden email]> wrote:
Any reason why you can't implement these as extension methods?

/Jesper Nordenberg

Rex Kerr skrev 2010-12-23 23:46:
There are a bunch of collections methods that could be implemented as

in-place operations on mutable versions of the collection, but currently
are not.

Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: In-place mutable operations

Nathan Bronson-2
In reply to this post by Rex Kerr-2
The inPlace view is nice.  Object creation is not inevitable and innards
access is possible.  The concrete implementation can implement both the
inPlace view and the mutable collection, with the extra methods hidden
by returning the generic trait from the factory method.  The
implementation of the inPlace method can then just return this.

As a concrete example, ScalaSTM has a method on trait Ref[A] that
returns a Ref.View[A] (and vice versa), but both traits are implemented
using a single instance.

 - Nathan

On Thu, 2010-12-23 at 18:26 -0500, Rex Kerr wrote:

> On Thu, Dec 23, 2010 at 6:14 PM, Seth Tisue <[hidden email]> wrote:
>         >>>>> "Rex" == Rex Kerr <[hidden email]> writes:
>        
>          Rex> So I propose that the collections methods ought to have
>         a robust
>          Rex> set of in-place operations, possibly notated by
>         postfixing the
>          Rex> method with InPlace (or some other better word--maybe
>         the suffix
>          Rex> -ize?).  [...]
>        
>         I like it, but I also worry about namespace clutter.  Perhaps
>         a more
>         orthogonal design is possible.
>        
>         How about an inPlace method on mutable collections that
>         returns a kind
>         of view?  "View" isn't quite the right word, maybe.  Anyway,
>         operations
>         on this "view" would have the usual names, but would actually
>         alter the
>         original collection instead of constructing new ones.  So
>         instead of:
>        
>          mySeq.filterInPlace(myPredicate)
>        
>         you'd write:
>        
>          mySeq.inPlace.filter(myPredicate)
>
> I have considered this, and I certainly prefer it syntactically.
> (I've proposed that the same should be done for all the xOption
> methods that are inconsistently present and clutter the namespace.)
>
> The problem with doing so here is that you unavoidably have an object
> creation each time you ask for it inPlace, and there's usually not
> much point using mutable collections if you're not interested in
> efficiency.  Almost everything is conceptually easier with immutable
> collections.
>
> So I think I would want to test the performance each way (in the ideal
> high-performance case, i.e. with specialized primitives) before
> agreeing to one vs. the other.
>
>   --Rex
>
>


Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: In-place mutable operations

Daniel Sobral
In reply to this post by Rex Kerr-2
Not all can be implemented for all mutable collections, however. For instance, I think most of them are impossible to implement with LinkedList (for which you can't have any method that may remove the first element in-place).

On Thu, Dec 23, 2010 at 20:46, Rex Kerr <[hidden email]> wrote:
There are a bunch of collections methods that could be implemented as in-place operations on mutable versions of the collection, but currently are not.  Although I appreciate the peace of mind of using immutable collections, it is sometimes frustrating to have to implement a remap for the Nth time, and often I just end up using `Array` or something instead of a more convenient collection because I don't have access to all the methods necessary to make the mutable version fast.

So I propose that the collections methods ought to have a robust set of in-place operations, possibly notated by postfixing the method with InPlace (or some other better word--maybe the suffix -ize?).  These should include things like (for something both Shrinkable and Growable):

  collectInPlace(pf: PartialFunction[A, A])
  diffInPlace(xs: Seq[A])
  distinctInPlace
  dropInPlace(n: Int)
  dropRightInPlace(n: Int)
  dropWhileInPlace(f: A => Boolean)
  filterInPlace(f: A => Boolean)
  filterNotInPlace(f: A => Boolean)
  flatMapInPlace(f: A => Traversable[A])
  initInPlace
  intersectInPlace(xs: Seq[A])
  mapInPlace(f: A => A)
  reverseInPlace
  scanLeftInPlace(z: A)(f: (A,A) => A)
  scanRightInPlace(z: A)(f: (A,A) => A)
  tailInPlace
  unionInPlace(xs: Seq[A])

Without methods like these, the utility of the mutable collections is considerably curtailed, and also leads to mutable collections stored in mutable vars since it is so often easier to build a new mutable collection than to change the one that you've got to be what you need.

So, my questions are:
  (1) Is it agreed that something like this is a good idea?
  (2) Is it planned, and what is the timeframe?
  (3) How could one contribute to this happening sooner rather than later (if the desirability is agreed upon)?

--Rex



--
Daniel C. Sobral

I travel to the future all the time.
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: In-place mutable operations

Erik Engbrecht
It depends on how you define an element and what kind of consistency you want to provide.  If you want to get rid of the first item in the list, you can update the first node in the list so it points at the second item and the third node.  If there isn't a second item then the first node is cleared as is now Nil.  Of course if some other piece of code has a reference to the second node it is now hosed.

But basically you have to assume that the in-place updates are destructive and the only object that is guaranteed to remain valid is the one on which you called the method.  Either that or you can have the methods return an object, which may be new or not, and have the now be the only guaranteed valid reference to the collection.

There's lots of potential for ugliness but I'm pretty sure it can be done.  IIRC Common Lisp has both destructive and non-destructive functions for filtering, mapping, etc. a list.

On Thu, Dec 23, 2010 at 9:04 PM, Daniel Sobral <[hidden email]> wrote:
Not all can be implemented for all mutable collections, however. For instance, I think most of them are impossible to implement with LinkedList (for which you can't have any method that may remove the first element in-place).


On Thu, Dec 23, 2010 at 20:46, Rex Kerr <[hidden email]> wrote:
There are a bunch of collections methods that could be implemented as in-place operations on mutable versions of the collection, but currently are not.  Although I appreciate the peace of mind of using immutable collections, it is sometimes frustrating to have to implement a remap for the Nth time, and often I just end up using `Array` or something instead of a more convenient collection because I don't have access to all the methods necessary to make the mutable version fast.

So I propose that the collections methods ought to have a robust set of in-place operations, possibly notated by postfixing the method with InPlace (or some other better word--maybe the suffix -ize?).  These should include things like (for something both Shrinkable and Growable):

  collectInPlace(pf: PartialFunction[A, A])
  diffInPlace(xs: Seq[A])
  distinctInPlace
  dropInPlace(n: Int)
  dropRightInPlace(n: Int)
  dropWhileInPlace(f: A => Boolean)
  filterInPlace(f: A => Boolean)
  filterNotInPlace(f: A => Boolean)
  flatMapInPlace(f: A => Traversable[A])
  initInPlace
  intersectInPlace(xs: Seq[A])
  mapInPlace(f: A => A)
  reverseInPlace
  scanLeftInPlace(z: A)(f: (A,A) => A)
  scanRightInPlace(z: A)(f: (A,A) => A)
  tailInPlace
  unionInPlace(xs: Seq[A])

Without methods like these, the utility of the mutable collections is considerably curtailed, and also leads to mutable collections stored in mutable vars since it is so often easier to build a new mutable collection than to change the one that you've got to be what you need.

So, my questions are:
  (1) Is it agreed that something like this is a good idea?
  (2) Is it planned, and what is the timeframe?
  (3) How could one contribute to this happening sooner rather than later (if the desirability is agreed upon)?

--Rex



--
Daniel C. Sobral

I travel to the future all the time.

Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: In-place mutable operations

Rex Kerr-2
In reply to this post by Nathan Bronson-2
On Thu, Dec 23, 2010 at 7:24 PM, Nathan Bronson <[hidden email]> wrote:
The inPlace view is nice.  Object creation is not inevitable and innards
access is possible.  The concrete implementation can implement both the
inPlace view and the mutable collection, with the extra methods hidden
by returning the generic trait from the factory method.  The
implementation of the inPlace method can then just return this.

Oh, interesting!  I hadn't considered that.  I wonder if that violates the "namespace clutter" concern?  For, after all, the inPlace version would have all the clutter that people were worrying about.  But it would only be cluttered if you asked for it.  Hm.  I think I like it!

  --Rex

Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: In-place mutable operations

Rex Kerr-2
In reply to this post by Daniel Sobral
No, of course, many of these cannot be implemented for all collections.  For example, nothing that changes the size of the collection will work with Array; if a collection is not Shrinkable, then filter will not work, etc..

LinkedList is something of a special case, since it could be hard to empty.

  --Rex
 

On Thu, Dec 23, 2010 at 9:04 PM, Daniel Sobral <[hidden email]> wrote:
Not all can be implemented for all mutable collections, however. For instance, I think most of them are impossible to implement with LinkedList (for which you can't have any method that may remove the first element in-place).


On Thu, Dec 23, 2010 at 20:46, Rex Kerr <[hidden email]> wrote:
There are a bunch of collections methods that could be implemented as in-place operations on mutable versions of the collection, but currently are not.  Although I appreciate the peace of mind of using immutable collections, it is sometimes frustrating to have to implement a remap for the Nth time, and often I just end up using `Array` or something instead of a more convenient collection because I don't have access to all the methods necessary to make the mutable version fast.

So I propose that the collections methods ought to have a robust set of in-place operations, possibly notated by postfixing the method with InPlace (or some other better word--maybe the suffix -ize?).  These should include things like (for something both Shrinkable and Growable):

  collectInPlace(pf: PartialFunction[A, A])
  diffInPlace(xs: Seq[A])
  distinctInPlace
  dropInPlace(n: Int)
  dropRightInPlace(n: Int)
  dropWhileInPlace(f: A => Boolean)
  filterInPlace(f: A => Boolean)
  filterNotInPlace(f: A => Boolean)
  flatMapInPlace(f: A => Traversable[A])
  initInPlace
  intersectInPlace(xs: Seq[A])
  mapInPlace(f: A => A)
  reverseInPlace
  scanLeftInPlace(z: A)(f: (A,A) => A)
  scanRightInPlace(z: A)(f: (A,A) => A)
  tailInPlace
  unionInPlace(xs: Seq[A])

Without methods like these, the utility of the mutable collections is considerably curtailed, and also leads to mutable collections stored in mutable vars since it is so often easier to build a new mutable collection than to change the one that you've got to be what you need.

So, my questions are:
  (1) Is it agreed that something like this is a good idea?
  (2) Is it planned, and what is the timeframe?
  (3) How could one contribute to this happening sooner rather than later (if the desirability is agreed upon)?

--Rex



--
Daniel C. Sobral

I travel to the future all the time.

Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: In-place mutable operations

Ruediger Keller-2
In reply to this post by Rex Kerr-2

+1

Am 2010 12 23 23:46 schrieb "Rex Kerr" <[hidden email]>:
> There are a bunch of collections methods that could be implemented as
> in-place operations on mutable versions of the collection, but currently are
> not. Although I appreciate the peace of mind of using immutable
> collections, it is sometimes frustrating to have to implement a remap for
> the Nth time, and often I just end up using `Array` or something instead of
> a more convenient collection because I don't have access to all the methods
> necessary to make the mutable version fast.
>
> So I propose that the collections methods ought to have a robust set of
> in-place operations, possibly notated by postfixing the method with InPlace
> (or some other better word--maybe the suffix -ize?). These should include
> things like (for something both Shrinkable and Growable):
>
> collectInPlace(pf: PartialFunction[A, A])
> diffInPlace(xs: Seq[A])
> distinctInPlace
> dropInPlace(n: Int)
> dropRightInPlace(n: Int)
> dropWhileInPlace(f: A => Boolean)
> filterInPlace(f: A => Boolean)
> filterNotInPlace(f: A => Boolean)
> flatMapInPlace(f: A => Traversable[A])
> initInPlace
> intersectInPlace(xs: Seq[A])
> mapInPlace(f: A => A)
> reverseInPlace
> scanLeftInPlace(z: A)(f: (A,A) => A)
> scanRightInPlace(z: A)(f: (A,A) => A)
> tailInPlace
> unionInPlace(xs: Seq[A])
>
> Without methods like these, the utility of the mutable collections is
> considerably curtailed, and also leads to mutable collections stored in
> mutable vars since it is so often easier to build a new mutable collection
> than to change the one that you've got to be what you need.
>
> So, my questions are:
> (1) Is it agreed that something like this is a good idea?
> (2) Is it planned, and what is the timeframe?
> (3) How could one contribute to this happening sooner rather than later
> (if the desirability is agreed upon)?
>
> --Rex

Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

RE: In-place mutable operations

Chris Marshall
In reply to this post by Nathan Bronson-2
Perhaps I am misunderstanding the intent of the inPlace view, but I thought the suggestion was to have the view obey the usual collection contract. This, of course, is impossible because the in-place view could only support e.g. map(A => A) as opposed to map(A => B). So it seems that we still have to have a plethora of orthogonal, new traits:

trait InPlaceSequence { 
    def map(f : A => A)
    ... etc
}

And, of course, these we would also want to be able to call standard (non-mutative methods on), such as length/sum etc.

It seem's like the "unification" via these new views might actually be pretty ugly and complicated?

Chris


> Subject: Re: [scala-debate] In-place mutable operations
> From: [hidden email]
> To: [hidden email]
> CC: [hidden email]; [hidden email]
> Date: Thu, 23 Dec 2010 16:24:24 -0800
>
> The inPlace view is nice. Object creation is not inevitable and innards
> access is possible. 
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: In-place mutable operations

Daniel Sobral
In reply to this post by Rex Kerr-2
Actually, if a LinkedList points to itself it is considered to be empty. And the point of its value being mutable as well is well taken.

I do think Scala ought to have in-place methods, but I'd rather they go through a long incubation period before they enter the API, so as to decrease the chance of bad API decisions.

On Fri, Dec 24, 2010 at 02:42, Rex Kerr <[hidden email]> wrote:
No, of course, many of these cannot be implemented for all collections.  For example, nothing that changes the size of the collection will work with Array; if a collection is not Shrinkable, then filter will not work, etc..

LinkedList is something of a special case, since it could be hard to empty.

  --Rex
 

On Thu, Dec 23, 2010 at 9:04 PM, Daniel Sobral <[hidden email]> wrote:
Not all can be implemented for all mutable collections, however. For instance, I think most of them are impossible to implement with LinkedList (for which you can't have any method that may remove the first element in-place).


On Thu, Dec 23, 2010 at 20:46, Rex Kerr <[hidden email]> wrote:
There are a bunch of collections methods that could be implemented as in-place operations on mutable versions of the collection, but currently are not.  Although I appreciate the peace of mind of using immutable collections, it is sometimes frustrating to have to implement a remap for the Nth time, and often I just end up using `Array` or something instead of a more convenient collection because I don't have access to all the methods necessary to make the mutable version fast.

So I propose that the collections methods ought to have a robust set of in-place operations, possibly notated by postfixing the method with InPlace (or some other better word--maybe the suffix -ize?).  These should include things like (for something both Shrinkable and Growable):

  collectInPlace(pf: PartialFunction[A, A])
  diffInPlace(xs: Seq[A])
  distinctInPlace
  dropInPlace(n: Int)
  dropRightInPlace(n: Int)
  dropWhileInPlace(f: A => Boolean)
  filterInPlace(f: A => Boolean)
  filterNotInPlace(f: A => Boolean)
  flatMapInPlace(f: A => Traversable[A])
  initInPlace
  intersectInPlace(xs: Seq[A])
  mapInPlace(f: A => A)
  reverseInPlace
  scanLeftInPlace(z: A)(f: (A,A) => A)
  scanRightInPlace(z: A)(f: (A,A) => A)
  tailInPlace
  unionInPlace(xs: Seq[A])

Without methods like these, the utility of the mutable collections is considerably curtailed, and also leads to mutable collections stored in mutable vars since it is so often easier to build a new mutable collection than to change the one that you've got to be what you need.

So, my questions are:
  (1) Is it agreed that something like this is a good idea?
  (2) Is it planned, and what is the timeframe?
  (3) How could one contribute to this happening sooner rather than later (if the desirability is agreed upon)?

--Rex



--
Daniel C. Sobral

I travel to the future all the time.




--
Daniel C. Sobral

I travel to the future all the time.
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: In-place mutable operations

Rex Kerr-2
In reply to this post by Chris Marshall
On Fri, Dec 24, 2010 at 6:23 AM, Chris Marshall <[hidden email]> wrote:
Perhaps I am misunderstanding the intent of the inPlace view, but I thought the suggestion was to have the view obey the usual collection contract. This, of course, is impossible because the in-place view could only support e.g. map(A => A) as opposed to map(A => B).

That's not impossible because of erasure.  A simple cast will do the trick.  It _would_ be necessary to reassign the collection at the other end, which is probably too undesirable of a use case to admit, however.

But if we used Nathan's suggestion, the names would have to be different anyway, since the whole point of inheritance is that something typed as a superclass uses the subclass version of the method.  So it would just be a trick to keep the namespace pollution out of view until you really wanted it.

  --Rex

Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: In-place mutable operations

Tony Morris
In reply to this post by Ruediger Keller-2

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Abstract on the type-constructor and have the best of all worlds.
Scala has type-safe higher-order polymorphism after all, one of its
most compelling
features.

On 24/12/10 19:31, Ruediger Keller wrote:
>
> +1
>
> Am 2010 12 23 23:46 schrieb "Rex Kerr" <[hidden email]
> [hidden email]>:
>> There are a bunch of collections methods that could be
>> implemented as in-place operations on mutable versions of the
>> collection, but
> currently are
>> not. Although I appreciate the peace of mind of using immutable
>> collections, it is sometimes frustrating to have to implement a
> remap for
>> the Nth time, and often I just end up using `Array` or something
> instead of
>> a more convenient collection because I don't have access to all
> the methods
>> necessary to make the mutable version fast.
>>
>> So I propose that the collections methods ought to have a robust
> set of
>> in-place operations, possibly notated by postfixing the method
> with InPlace
>> (or some other better word--maybe the suffix -ize?). These
>> should
> include
>> things like (for something both Shrinkable and Growable):
>>
>> collectInPlace(pf: PartialFunction[A, A]) diffInPlace(xs: Seq[A])
>> distinctInPlace dropInPlace(n: Int) dropRightInPlace(n: Int)
>> dropWhileInPlace(f: A => Boolean) filterInPlace(f: A => Boolean)
>> filterNotInPlace(f: A => Boolean) flatMapInPlace(f: A =>
>> Traversable[A]) initInPlace intersectInPlace(xs: Seq[A])
>> mapInPlace(f: A => A) reverseInPlace scanLeftInPlace(z: A)(f:
>> (A,A) => A) scanRightInPlace(z: A)(f: (A,A) => A) tailInPlace
>> unionInPlace(xs: Seq[A])
>>
>> Without methods like these, the utility of the mutable
>> collections is considerably curtailed, and also leads to mutable
>> collections
> stored in
>> mutable vars since it is so often easier to build a new mutable
> collection
>> than to change the one that you've got to be what you need.
>>
>> So, my questions are: (1) Is it agreed that something like this
>> is a good idea? (2) Is it planned, and what is the timeframe?
>> (3) How could one contribute to this happening sooner rather
>> than
> later
>> (if the desirability is agreed upon)?
>>
>> --Rex
>



- --
Tony Morris
http://tmorris.net/

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.10 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iEYEARECAAYFAk0WcBsACgkQmnpgrYe6r60s/ACdH12ZSzV3Peyo8sdUa9um/eN2
Dv0AnjZbFuAju3jGBQYOJ3WHVI6jUSwL
=nYx5
-----END PGP SIGNATURE-----

Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: In-place mutable operations

Daniel Sobral
In reply to this post by Rex Kerr-2
By the way, add "sort" to that list. After all, the idea of changing the name to "sorted" in Scala 2.8.0 was that "sort" would be reserved for in-place, like update/updated. Or so I assume. :-)

On Thu, Dec 23, 2010 at 20:46, Rex Kerr <[hidden email]> wrote:
There are a bunch of collections methods that could be implemented as in-place operations on mutable versions of the collection, but currently are not.  Although I appreciate the peace of mind of using immutable collections, it is sometimes frustrating to have to implement a remap for the Nth time, and often I just end up using `Array` or something instead of a more convenient collection because I don't have access to all the methods necessary to make the mutable version fast.

So I propose that the collections methods ought to have a robust set of in-place operations, possibly notated by postfixing the method with InPlace (or some other better word--maybe the suffix -ize?).  These should include things like (for something both Shrinkable and Growable):

  collectInPlace(pf: PartialFunction[A, A])
  diffInPlace(xs: Seq[A])
  distinctInPlace
  dropInPlace(n: Int)
  dropRightInPlace(n: Int)
  dropWhileInPlace(f: A => Boolean)
  filterInPlace(f: A => Boolean)
  filterNotInPlace(f: A => Boolean)
  flatMapInPlace(f: A => Traversable[A])
  initInPlace
  intersectInPlace(xs: Seq[A])
  mapInPlace(f: A => A)
  reverseInPlace
  scanLeftInPlace(z: A)(f: (A,A) => A)
  scanRightInPlace(z: A)(f: (A,A) => A)
  tailInPlace
  unionInPlace(xs: Seq[A])

Without methods like these, the utility of the mutable collections is considerably curtailed, and also leads to mutable collections stored in mutable vars since it is so often easier to build a new mutable collection than to change the one that you've got to be what you need.

So, my questions are:
  (1) Is it agreed that something like this is a good idea?
  (2) Is it planned, and what is the timeframe?
  (3) How could one contribute to this happening sooner rather than later (if the desirability is agreed upon)?

--Rex



--
Daniel C. Sobral

I travel to the future all the time.
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: In-place mutable operations

Paul Phillips-3
On Sun, Dec 26, 2010 at 07:07:03PM -0200, Daniel Sobral wrote:
> By the way, add "sort" to that list. After all, the idea of changing
> the name to "sorted" in Scala 2.8.0 was that "sort" would be reserved
> for in-place, like update/updated. Or so I assume. :-)

Nope.  It was only that "sort" was already taken.  Which is not to say
that we couldn't retrofit that explanation after the deprecated sort's
grace period expires.

--
Paul Phillips      | Those who can make you believe absurdities
Future Perfect     | can make you commit atrocities.
Empiricist         |     -- Voltaire
i'll ship a pulp   |----------* http://www.improving.org/paulp/ *----------
Loading...