Working with immutable collections

[Joa Ebert]

Hi,

starting to dig into guava I wonder what the general contract is to add an element to an already existing immutable collection.

Of course that addition would not modify the existing object.

final Set<A> set0 = ImmutableSet.of();

final Set<A> set1 = set0.add2(new A());//does not modify set0, returns a new set1 which is a superset to set0

System.out.println(set0.size()) //0

System.out.println(set1.size()) //1 

I am quite sure that you have thought about the use case of an immutable collection that one might want to build dynamically for instance. For that particular case I think that the builder is used(?).

List<A> buildList(final int n, final ImmutableList.Builder<A> builder) { 

  if(n == 0) { return builder.build(); }

  else { return buildList(n - 1, builder.add(new A()); }

}

But should I also use the builder if I already have an immutable list and want to add only a single element to it? E.g.

final ImmutableSet.Builder<A> builder = ImmutableSet.builder()

builder.addAll(set0);

builder.add(new A());

final Set<A> set1 = builder.build();

I am just asking because it would add unnecessary boilerplate to the code and if that is the proposed way to handle this.

I would expect a helper method like set1 = Sets.add(set0, value). But again that is why I am asking. I probably missed something in the docs.

Best,

Joa Ebert

[Fred Faber]

I think you'll be best off with the builder, but in a terser form than you show:

From:

final ImmutableSet.Builder<A> builder = ImmutableSet.builder()

builder.addAll(set0);

builder.add(new A());

final Set<A> set1 = builder.build();

To:

final ImmutableSet<A> set1 = ImmutableSet.builder()

    .addAll(set0)

    .add(new A())

    .build();

-Fred

--
guava-...@googlegroups.com.
http://groups.google.com/group/guava-discuss?hl=en
unsubscribe: guava-discus...@googlegroups.com
 
This list is for discussion; for help, post to Stack Overflow instead:
http://stackoverflow.com/questions/ask
Use the tag "guava".

[Louis Wasserman]

I have to also add: if you want to add elements, then why did you use an immutable collection in the first place?

Louis Wasserman
wasserm...@gmail.com
http://profiles.google.com/wasserman.louis

[Nikolas Everett]

Yeah!  Why not just make a standard collection and wrap it in a Collection.immutableXXX?  If you are accumulating stuff then that is really the way to go.

[Robert Konigsberg]

I would prefer to have a better understanding of what you're trying to do -- why do you want an immutable collection in this case?

Though I disagree with Nikola -- the Collections.immuable* methods should basically be avoided simply because of the benefits that come from the immutable collections.

Fred's basically got it for you there, though if you control construction of set0, you could just reuse the builder...

ImmutableSet.Builder builder = ImmutableSet.builder( ... );
final ImmutableSet<A> set0 = builder.build();
final ImmutableSet<A> set1 = builder.add(new A()).build();

--

guava-...@googlegroups.com.
http://groups.google.com/group/guava-discuss?hl=en
unsubscribe: guava-discus...@googlegroups.com
 
This list is for discussion; for help, post to Stack Overflow instead:
http://stackoverflow.com/questions/ask
Use the tag "guava".

--
Robert Konigsberg
konig...@gmail.com

[Joa Ebert]

Fred: Thank you, the short builder syntax it is then.

Louis & Nik: Because an immutable data structure makes a lot of sense for me and simplifies the code a lot.

[Joa Ebert]

Okay, I will quickly explain why I would like to use an immutable list.

I have a class Signal with observers attached. Signal can dispatch a message to all its observers. Anyone can add or remove observers to the signal, or clear the list of observers.

During the dispatch phase, the state of the observer list does not change and is only taken into account in the next phase. 

In pseudo code:

o1.exec = signal.remove(o2)

o2.exec = signal.add(o3);

signal.add(o1);

signal.add(o2);

signal.dispatch(); //o2 is executed, o3 is not executed

signal.dispatch(); //o2 has been removed, o3 is executed because it has been added in the previous dispatch phase.

Here is pseudo code for an implementation that uses immutable lists:

Signal<A> {

  List<Observer<A>> list = Nil

  add(Observer<A> observer) { list = list.add(observer) }

  remove(Observer<A> observer) { list = list.remove(observer) }

  clear() { list = Nil }

  dispatch(A value) {

     List<Observer<A>> listSnapshot = list

     for(Observer<A> o : listSnapshot) { o.exec(value) }

  }  

}

How would this work with a mutable list? Well obviously one can clone the list in the beginning of dispatch to make sure you are working with a snapshot of the state. But then I would ask: why are you not using an immutable list in the first place? The memory footprint would be much better. Of course then you could say: Use a boolean to capture when you are in the dispatch phase, and clone the list only as needed. That is correct but would make the code larger and unnecessarily complex.

Best,

Joa

[Robert Konigsberg]

Aha! Don't use any of these -- use CopyOnWriteArrayList -- it's perfect for the listener idiom 99% of the time.

--

guava-...@googlegroups.com.
http://groups.google.com/group/guava-discuss?hl=en
unsubscribe: guava-discus...@googlegroups.com
 
This list is for discussion; for help, post to Stack Overflow instead:
http://stackoverflow.com/questions/ask
Use the tag "guava".

--
Robert Konigsberg
konig...@gmail.com

[Joa Ebert]

Thank you Robert, it is definitely an option.

Is there any particular reason you voted against more powerful immutable collections (add, remove, filter, ...)? 

[Torbjorn Gannholm]

I'd say it's a question of how much API is worth maintaining. We put in things that add real power and get a lot of usage. No point in throwing in a whole kitchen sink.

ImmutableSet.builder().addAll(Iterables.filter(oldSet, myFilter)).build()

works pretty well, for example. Usually you probably don't even need to construct a filtered set, but are fine with just Iterables.filter(oldSet, myFilter)

/tobe

On Wed, Dec 29, 2010 at 12:09 PM, Joa Ebert <joae...@googlemail.com> wrote:

Thank you Robert, it is definitely an option.

Is there any particular reason you voted against more powerful immutable collections (add, remove, filter, ...)? 

--

[Robert Konigsberg]

I strongly recommend that you get a copy of Java Concurency in Practice -- and then _read it_. :) It exactly covers this. Seriously, it's exactly what it's for. The only reason you might not want it is because the number of mutations to the list is so frequent that COWAL is no longer efficient. Keep in mind that with your solution as-is, you aren't guaranteed thread safety, and could lose mutation operations. Or are you not interested in thread safety?

On Wed, Dec 29, 2010 at 3:09 AM, Joa Ebert <joae...@googlemail.com> wrote:

Thank you Robert, it is definitely an option.

Is there any particular reason you voted against more powerful immutable collections (add, remove, filter, ...)? 

--

guava-...@googlegroups.com.
http://groups.google.com/group/guava-discuss?hl=en
unsubscribe: guava-discus...@googlegroups.com
 
This list is for discussion; for help, post to Stack Overflow instead:
http://stackoverflow.com/questions/ask
Use the tag "guava".

--
Robert Konigsberg
konig...@gmail.com

[Louis Wasserman]

Just checking -- Joa, are you aware of the existence of http://download.oracle.com/javase/1.5.0/docs/api/java/util/concurrent/CopyOnWriteArrayList.html in the first place?

Louis Wasserman
wasserm...@gmail.com
http://profiles.google.com/wasserman.louis

[Johan Van den Neste]

Related, I would love to see persistent collections added to guava.

Such as http://code.google.com/p/pcollections/

--
Johan Van den Neste

[Dimitris Andreou]

I'd love to see good persistent collections, at the quality level of guava, but probably guava would not be the proper place for this. With guava's popularity, putting these there would just encourage overusing them - and from my scala experience I learned that many people would love to start choosing suboptimal structures just for the sake of "purity". Persistent structures border (and not coincide, since classic work on persistent structures actually depends on mutations) with functional programming, which can trigger that effect.

There are various graph algorithms though that cannot be implemented efficiently without persistent collections. A good example is finding k shortest paths, instead of just one (so to have some alternatives) - this needs persistent heaps. Another example is simply depth-first traversals, where persistent stacks can offer richer semantics: instead of just visiting nodes, client code can safely be visiting the whole paths from the root, basically for free. 

[Torbjorn Gannholm]

On Thu, Dec 30, 2010 at 11:00 AM, Dimitris Andreou <jim.a...@gmail.com> wrote:

I'd love to see good persistent collections, at the quality level of guava, but probably guava would not be the proper place for this. With guava's popularity, putting these there would just encourage overusing them - and from my scala experience I learned that many people would love to start choosing suboptimal structures just for the sake of "purity". Persistent structures border (and not coincide, since classic work on persistent structures actually depends on mutations) with functional programming, which can trigger that effect.

There are various graph algorithms though that cannot be implemented efficiently without persistent collections. A good example is finding k shortest paths, instead of just one (so to have some alternatives) - this needs persistent heaps. Another example is simply depth-first traversals, where persistent stacks can offer richer semantics: instead of just visiting nodes, client code can safely be visiting the whole paths from the root, basically for free. 

Do you have some pointers for this?
/tobe
 

[Dimitris Andreou]

On Thu, Dec 30, 2010 at 2:10 AM, Torbjorn Gannholm <to...@google.com> wrote:

On Thu, Dec 30, 2010 at 11:00 AM, Dimitris Andreou <jim.a...@gmail.com> wrote:

I'd love to see good persistent collections, at the quality level of guava, but probably guava would not be the proper place for this. With guava's popularity, putting these there would just encourage overusing them - and from my scala experience I learned that many people would love to start choosing suboptimal structures just for the sake of "purity". Persistent structures border (and not coincide, since classic work on persistent structures actually depends on mutations) with functional programming, which can trigger that effect.

There are various graph algorithms though that cannot be implemented efficiently without persistent collections. A good example is finding k shortest paths, instead of just one (so to have some alternatives) - this needs persistent heaps. Another example is simply depth-first traversals, where persistent stacks can offer richer semantics: instead of just visiting nodes, client code can safely be visiting the whole paths from the root, basically for free. 

Do you have some pointers for this?
/tobe
 

I'll assume that you refer to the shortest paths: this is what I had in mind: Finding the k Shortest Paths (pdf), specifically section 2.

[Torbjorn Gannholm]

On Thu, Dec 30, 2010 at 11:28 AM, Dimitris Andreou <jim.a...@gmail.com> wrote:

On Thu, Dec 30, 2010 at 2:10 AM, Torbjorn Gannholm <to...@google.com> wrote:

On Thu, Dec 30, 2010 at 11:00 AM, Dimitris Andreou <jim.a...@gmail.com> wrote:

I'd love to see good persistent collections, at the quality level of guava, but probably guava would not be the proper place for this. With guava's popularity, putting these there would just encourage overusing them - and from my scala experience I learned that many people would love to start choosing suboptimal structures just for the sake of "purity". Persistent structures border (and not coincide, since classic work on persistent structures actually depends on mutations) with functional programming, which can trigger that effect.

There are various graph algorithms though that cannot be implemented efficiently without persistent collections. A good example is finding k shortest paths, instead of just one (so to have some alternatives) - this needs persistent heaps. Another example is simply depth-first traversals, where persistent stacks can offer richer semantics: instead of just visiting nodes, client code can safely be visiting the whole paths from the root, basically for free. 

Do you have some pointers for this?
/tobe
 

I'll assume that you refer to the shortest paths: this is what I had in mind: Finding the k Shortest Paths (pdf), specifically section 2.

Thanks.

I'm still having a problem seeing that persistent collections could be useful (and used for the right reasons) in a larger context. I assume that when writing an optimal algorithm one would tend to write a specialized data structure anyway.

A persistent stack seems to give a large savings, but I'm not sure I see it being very useful

Is there any particular structure that you see as both giving a significant savings and a high utility (i.e. all other existing implementations would be a significantly worse choice)?

/tobe
 

[Dimitris Andreou]

On Thu, Dec 30, 2010 at 2:47 AM, Torbjorn Gannholm <to...@google.com> wrote:

On Thu, Dec 30, 2010 at 11:28 AM, Dimitris Andreou <jim.a...@gmail.com> wrote:

On Thu, Dec 30, 2010 at 2:10 AM, Torbjorn Gannholm <to...@google.com> wrote:

On Thu, Dec 30, 2010 at 11:00 AM, Dimitris Andreou <jim.a...@gmail.com> wrote:

I'd love to see good persistent collections, at the quality level of guava, but probably guava would not be the proper place for this. With guava's popularity, putting these there would just encourage overusing them - and from my scala experience I learned that many people would love to start choosing suboptimal structures just for the sake of "purity". Persistent structures border (and not coincide, since classic work on persistent structures actually depends on mutations) with functional programming, which can trigger that effect.

There are various graph algorithms though that cannot be implemented efficiently without persistent collections. A good example is finding k shortest paths, instead of just one (so to have some alternatives) - this needs persistent heaps. Another example is simply depth-first traversals, where persistent stacks can offer richer semantics: instead of just visiting nodes, client code can safely be visiting the whole paths from the root, basically for free. 

Do you have some pointers for this?
/tobe
 

I'll assume that you refer to the shortest paths: this is what I had in mind: Finding the k Shortest Paths (pdf), specifically section 2.

Thanks.

I'm still having a problem seeing that persistent collections could be useful (and used for the right reasons) in a larger context. I assume that when writing an optimal algorithm one would tend to write a specialized data structure anyway.

I agree with the scope, these are just needed for a small minority compared to java/guava collections. That said, it's still a pity, in the java community that is in the millions, to be working on a problem, then realizing that a persistent structure is needed, then be sidetracked for a couple of weeks producing a so-and-so implementation. 

 

A persistent stack seems to give a large savings, but I'm not sure I see it being very useful

I don't know. I only found it useful in graph algorithms, for representing/combining paths (persistent stack is not too useful for combining paths either, since it can only append a single element, but this can be easily generalized to a rope-like structure with O(1) appending/prepending of other ropes; only the shape of the implicit tree would change, consecutive versions of ropes wouldn't have to form a right-leaning tree, as consecutive versions of a stack would). By the way, scala guys use it passionately as a replacement for java.util.ArrayList, but this just wastes memory.

 

Is there any particular structure that you see as both giving a significant savings and a high utility (i.e. all other existing implementations would be a significantly worse choice)?

I won't suggest a specific structure, but I've ran many times into the need of creating a new set that is basically some existing one, with some additions and/or removals, but without being able to destroy the original set. I typically end up copying HashSets, which is painfully inefficient when the changes are small. But: (1) I don't know if this is a common problem for other people too, and (2) one could try to simulate some of the benefits of a persistent structure by using the union/difference/etc views in Sets, but such an approach has tricky performance implications (especially so if views are recursively built/pile up).  

Other than that, I can't think of anything important right now, if this carries enough importance at all.

Dimitris

[Louis Wasserman]

As a programmer with a purely functional background, I should mention that the asymptotics and performance of well-designed persistent map implementations are essentially the same as those of TreeMap.

Louis Wasserman
wasserm...@gmail.com
http://profiles.google.com/wasserman.louis

[Eric Winter]

Made me wonder of a couple methods on ImmutableCollection

ImmutableCollection<String> c1 = ...
ImmutableCollection<String> c2 = c1.with("Hello", "World");
ImmutableCollection<String> c3 = c2.without("World");
ImmutableCollection<String> c4 = c1.withAll(myIterable);

[Daniel Yokomizo]

On Thu, Dec 30, 2010 at 8:00 AM, Dimitris Andreou <jim.a...@gmail.com> wrote:
> Persistent structures border (and not coincide, since classic work on persistent
> structures actually depends on mutations) with functional programming, which
> can trigger that effect.

Just for the record, there's some good research on purely function
data structures. The Okasaki paper (and book with same name) is a
great starter:

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.62.505

Best regards,
Daniel Yokomizo.

[Johan Van den Neste]

>> Related, I would love to see persistent collections added to guava.
>>
>> Such as http://code.google.com/p/pcollections/
>

> Can you provide a convincing use case as to what it allows you to
> accomplish?

Immutable collections in general make concurrency easy. Persistent
collections have pretty good performance characteristics -- often good
enough to suit needs. Graph and search algorithms become easier to
implement, especially when you want them to be concurrent. You might
win some by implementing specialized structures, but often it won't be
much and chances are it's just not worth it.

[Johan Van den Neste]

> As a programmer with a purely functional background, I should mention that
> the asymptotics and performance of well-designed persistent map
> implementations are essentially the same as those of TreeMap.

I'd say they typically perform much better than that. At least the
implementations used in Clojure and Scala 2.8 do.

log32(n) vs log2(n)

[Dimitris Andreou]

On Fri, Dec 31, 2010 at 3:01 AM, Johan Van den Neste <jvdn...@gmail.com> wrote:

> As a programmer with a purely functional background, I should mention that
> the asymptotics and performance of well-designed persistent map
> implementations are essentially the same as those of TreeMap.

I'd say they typically perform much better than that. At least the
implementations used in Clojure and Scala 2.8 do.

This remains to be proved.

 

log32(n) vs log2(n) 

This is just a factor of 5. And in the TreeMap case, the constant is basically a comparison and a dereference. (And to make it more an oranges to oranges comparison, we would use a TreeMap<Integer, Collection<V>>, where the key would be the hashcode, so even the comparison would be just between integers). So, in a trie with 32-element branch nodes, can one branch faster (let alone much faster) than a little more than 5 comparisons and dereferences? I'd like to see that. 

[Kevin Bourrillion]

On Thu, Dec 30, 2010 at 2:00 AM, Dimitris Andreou <jim.a...@gmail.com> wrote:

I'd love to see good persistent collections, at the quality level of guava, but probably guava would not be the proper place for this. With guava's popularity, putting these there would just encourage overusing them - and from my scala experience I learned that many people would love to start choosing suboptimal structures just for the sake of "purity". Persistent structures border (and not coincide, since classic work on persistent structures actually depends on mutations) with functional programming, which can trigger that effect.

 

This is basically my position.

--
Kevin Bourrillion @ Google
http://guava-libraries.googlecode.com

[ro...@google.com]

One more advantage of 32-element branching factor is cache locality for frequent traversal or just a bunch of localized accesses by index.

But, if the structure is much more often written to than is accessed, then the optimal branching factors should be lower, maybe even just 2 or 4. I kind of miss that this is not configurable in Scala.

>>>>>>> >>> unsubscribe: guava-discuss+unsub...@googlegroups.com

>>>>>>> >>>
>>>>>>> >>> This list is for discussion; for help, post to Stack Overflow
>>>>>>> >>> instead:
>>>>>>> >>> http://stackoverflow.com/questions/ask
>>>>>>> >>> Use the tag "guava".
>>>>>>> >>
>>>>>>> >>
>>>>>>> >>
>>>>>>> >> --
>>>>>>> >> Robert Konigsberg
>>>>>>> >> konig...@gmail.com
>>>>>>> >>
>>>>>>> >> --
>>>>>>> >> guava-...@googlegroups.com.
>>>>>>> >> http://groups.google.com/group/guava-discuss?hl=en

>>>>>>> >> unsubscribe: guava-discuss+unsub...@googlegroups.com

>>>>>>> >>
>>>>>>> >> This list is for discussion; for help, post to Stack Overflow
>>>>>>> >> instead:
>>>>>>> >> http://stackoverflow.com/questions/ask
>>>>>>> >> Use the tag "guava".
>>>>>>> >
>>>>>>> > --
>>>>>>> > guava-...@googlegroups.com.
>>>>>>> > http://groups.google.com/group/guava-discuss?hl=en

>>>>>>> > unsubscribe: guava-discuss+unsub...@googlegroups.com

>>>>>>> >
>>>>>>> > This list is for discussion; for help, post to Stack Overflow
>>>>>>> > instead:
>>>>>>> > http://stackoverflow.com/questions/ask
>>>>>>> > Use the tag "guava".
>>>>>>> >
>>>>>>>
>>>>>>> --
>>>>>>> guava-...@googlegroups.com.
>>>>>>> http://groups.google.com/group/guava-discuss?hl=en

>>>>>>> unsubscribe: guava-discuss+unsub...@googlegroups.com

>>>>>>>
>>>>>>> This list is for discussion; for help, post to Stack Overflow
>>>>>>> instead:
>>>>>>> http://stackoverflow.com/questions/ask
>>>>>>> Use the tag "guava".
>>>>>>
>>>>>> --
>>>>>> guava-...@googlegroups.com.
>>>>>> http://groups.google.com/group/guava-discuss?hl=en

>>>>>> unsubscribe: guava-discuss+unsub...@googlegroups.com

>>>>>>
>>>>>> This list is for discussion; for help, post to Stack Overflow instead:
>>>>>> http://stackoverflow.com/questions/ask
>>>>>> Use the tag "guava".
>>>>>
>>>>
>>>> --
>>>> guava-...@googlegroups.com.
>>>> http://groups.google.com/group/guava-discuss?hl=en

>>>> unsubscribe: guava-discuss+unsub...@googlegroups.com