Immutable List/Map

[DartBot]

This issue was originally filed by [email protected]

---

Collection interface allows immutable implementations.

But List interface defines methods like add or remove. Including an immutable version of a sequence (with [], getRange, indexOf) could be useful for cases in which one need to represent a sequence of elements without allowing modifications.

[DartBot]

This comment was originally written by [email protected]

---

If there is an immutable list, String could implement that interface

[DartBot]

This comment was originally written by [email protected]

---

Removed Type-Defect label.
Added Type-Enhancement, Area-Library, Triaged labels.

[DartBot]

This comment was originally written by @yjbanov

---

Here's my proposal for an implementation of read-only collection interfaces (with minimal disruptions to the current status quo and with programmer familiarity in mind) along with a working prototype. The discussion on misc mailing list was mostly favorable:

Discussions:
 https://groups.google.com/a/dartlang.org/group/misc/browse_thread/thread/4c94c9b11c21290c/e3b0b4ddbf96dd53?lnk=gst&q=read-only#e3b0b4ddbf96dd53
 https://groups.google.com/a/dartlang.org/group/misc/browse_thread/thread/92939371911ad67c/492db8eab1ec629b

Proposed class hierarchy:
 http://goo.gl/MlQkL

Prototype code:
 http://code.google.com/p/yegor-experimental/source/browse/#git%2Fdart%2Fcollections

Also, it would be nice to distinguish true immutability from read-only interfaces. The proposal is for the latter, not the former. The two concepts are independent of each other, although very related. It is highly desirable that immutable classes only provide read-only interfaces. Unfortunately, I refer to read-only interfaces as immutable in my code comments. I'm planning to fix that.

Thanks,

Yegor

[DartBot]

This comment was originally written by [email protected]

---

(Disclosure: my background is C#, but I am very interested in Dart in that it has the potential to unite the client and server code bases. I believe that C# is a great language with a terrible framework, and do not want to say the same of Dart.)

I would like to add that the availability of immutable interfaces is important in that it dramatically improves the expressiveness of your interfaces. Usually when you publicly expose a collection, you want it to be immutable, so what ends up happening is everything returns Collection or Iterable (this is also the case in C#).

If you have immutable interfaces, your interfaces become vastly more expressive. The Iterable and Collection types tell a programmer absolutely nothing beyond the fact that you have a bunch of objects, whereas with immutable interfaces for the standard abstract data types, the consumer of your interface immediately knows everything that those interfaces entail:

• Set: every object is unique
• List: the collection is in some kind of order
• OrderedSet: both of the above

This may seem like small details, but in actuality there is a wealth of valuable information here - particularly when developing complex models. If you consider reflection-orientated uses for this information (think ORMs such as [N]Hibernate), the uses become particularly evident.

Now, while the class hierarchy posted by Yegor is pretty much spot-on in terms of structure, I would suggest that it is preferable to give the immutable interface the common name; the reason being that you want the selection of a mutable type to be a conscious decision on the part of the programmer per the 'make it hard to write bad code' mantra. Thus I would suggest the a structure along the following lines:

Iterable <-- Collection <-- List <-- MutableList

Implementation should be fairly easy with some refactoring in that all that has to happen is make the existing interfaces implement the immutable ones, and move all of the 'read' methods to the immutable interfaces. No code breakage, although there are probably a large number of cases where the newly created immutable interfaces should be used in lieu of the mutable ones.

@yegor: I think what you may be trying to communicate is 'this will never change' as opposed to 'you cannot change this'. The former is a difficult guarantee to make because there is no real facility to do so. You can define a type ListThatWillNeverChange, but there is no guarantee that the returned object's behavior will not change beyond the fact that its type name claims it to be so.

[DartBot]

This comment was originally written by @yjbanov

---

James, your suggestions are great. However, some of Dart's goals make it a little hard to go the whole 9 yards with this. Please, have a look at the mailing list discussions (links above). There you will find reasons for reserving common names for writable interfaces, as well as why I switched from "immutable" to "read-only".

Yegor

PS: The issue tracker is a bad place for design discussions. Why don't you post your thoughts to the mailing list instead of here (but provide cross-links)? Many more people would get a chance to read and comment on your ideas.

[sethladd]

Issue #3700 has been merged into this issue.

[DartBot]

This comment was originally written by [email protected]

---

I'd like to see this solved not with new container types but with an immutable type extension, akin to const. Where const suggests the reference is not mutable, immutable would suggest the contents would not be mutable.

This is important as it allows the VM and compiler to make assumptions and introduce new optimizations.

[kevmoo]

FYI: Sequence<T> in r13806 gets me half way there with List.

[sethladd]

I know people are asking for something like Sequence. However, I can point out that there is an UnmodifiableListView class here: http://api.dartlang.org/docs/releases/latest/dart_collection/UnmodifiableListView.html

(not sure why there isn't an UnmodifiableMapView, I'll open a bug for that :)

CCing Florian to see if we should close this or keep this issue open.

---

cc @floitschG.

[DartBot]

This comment was originally written by [email protected]

---

I like Scala's class hierarchy and immutable/mutable classes a lot, e.g.:

collection.Map -- can be mutable or immutable or read-only, exposes no mutating functions
collection.immutable.Map -- is immutable, extends collections.Map
collection.mutable.Map -- is mutable, extends collections.Map

Here's an overview of what the Scala people have built; it's amazingly well designed IMO:
http://docs.scala-lang.org/overviews/collections/overview.html

[floitschG]

Agreed that the Scala hierarchy is good.
In Dart we decided to keep the number of classes relatively small. This, of course, comes with some limitations. It's the same trade-off as between sound type-system and unsound (or optional) type-system.

[sethladd]

The Quiver library might be a good place to try immutable collection classes. https://github.com/google/quiver-dart Pull Requests welcome.

[sethladd]

cc @justinfagnani.

[kevmoo]

I think most of these are covered by http://api.dartlang.org/docs/releases/latest/unmodifiable_collection.html

and http://api.dartlang.org/docs/releases/latest/dart_collection/UnmodifiableListView.html

The original request here was to have core interfaces without mutate methods. Sadly, this is not going to happen in V1. While it's possible to ship a List-like class without []=, remove, etc, it'll be a tough sell as a reusable Type.

Too many other method expect to get something of type List, etc.

[DartBot]

This comment was originally written by [email protected]

---

I think separate collections with distinct interfaces is exactly the way to go. The fact that Iterable does not have any mutating methods means they can all implement that. Methods that accept List should where possible be changed to accept Iterable, or you can call toList on the immutable type.

I am indeed trying to get these added to Quiver, we'll see how it goes :)

[DartBot]

This comment was originally written by [email protected]

---

There are methods like Map.from(Map other), that expect other Map as an parameter. These methods don't need a whole Map, they are just fine with "read-only" Map. However, it is not possible to me give them object that implements just the read functionality of Map, because it can't be derived from Map.

This is pity. I have to implement write methods that throw UnsupportedError. I feel this is somehow wrong.

[kevmoo]

I fought hard for this, but in the end adding a non-mutable layer to List|Map|Set added too many types to a core library that was already big.

---

Added NotPlanned label.

[DartBot]

This comment was originally written by @tkrotoff

---

When I want an immutable variable, I do:

final i = 10;
i = 11; // Error

If I want an immutable list, I would like to simply write:

final names = ['Anna', 'Nicolas'];
names.add('Thomas'); // Should give an error: cannot change length
names[1] = 'Thomas'; // Should give an error: cannot change content

[davidmorgan]

For the record, https://github.com/google/built_collection.dart is about as close as it's possible to get without changing the SDK.

For example, BuiltList.toList uses a copy-on-write wrapper to implement the List interface, so you can efficiently call a method that expects a List but does not need the mutating part of the interface.

[oetiker]

Note the comment in cd1be9d07df32413024fe5c4ae9c5c6017c2f2c8 regarding this issue is wrong ... it should NOT be closed. @athomas

[athomas]

@oetiker Thanks, we will remove the '#' signs from those messages in the future to avoid this from happening again.

[lrhn]

This change is not planned, and not likely to happen in the current Dart platform libraries.

Having multiple versions of List, say Sequence and List where the former is read-only and the latter is mutable, means that users need to decide which one to use for every occurrence of the type. Even if we don't actually make any objects that implement only Sequence, the API complexity still increases. We might want to change old code to use Sequence, but we can only do that if we already always return unmodifiable lists. We can't change a parameter of an instance method to Sequence because then it's a breaking change for an implementation of that interface to require a List. Migration of old code will not be pleasant, and likely not satisfactory in the end.
Also, it is not enough. We may also want a type like Array which is a mutable fixed length list. Modifiability of lists is not an either-or concern, we have degrees between immutable and growable lists. This ups the complexity cost again.

Should Sequence be a subtype of Iterable, or should it just have length and operator[]? In the latter case, String is a Sequence<String>, even if it is not an Iterable at all. A small marker-interface which represents the ability to do fast index lookup using integer indices, or a proper super-class of List with all the non-mutating non-Iterable members (operator[], operator+, asMap(), getRange, indexOf, lastIndexOf, indexWhere, lastIndexWhere, reversed, sublist - and of these, operator+, reversed and sublist would now have to return a Sequence instead).

All in all, the original arguments for having only one List interface still stands: The added complexity of having multiple types does not pay for itself. Users having to worry about the kind of list that they accept and/or provide is a mental cost that is unnecessary in the majority of cases. And, arguably, the unmodifiable list case exists already: Iterable.

The counter-argument would be that the increased static safety is worth the extra cost. You'll never get a run-time error from trying to modify a Sequence because that'll be a static error, the Sequence has no add method at all. And without implicit downcast, this subtyping won't be as error-prone by itself.

For now this issue can be closed.