Add a constructor for an empty growable list

[hacker1024]

Now that constructor tear-offs are a thing, a List constructor to create a blank, growable list would be useful.

My specific use-case for this is for a class that stores a collection of a generic type (like a List or Map). To ensure that it starts off with an empty collection, it takes a factory function in its constructor.

class Example<C> {
  final C collection;

  Example(C Function() collectionFactory) : collection = collectionFactory();
}

var mapExample = Example(Map.new); // This is fine
var listExample = Example(List.new); // This is deprecated

[lrhn]

Use List.empty. If we ever get to remove the List constructor, then after a while we might choose to repurpose. Until then List.empty is the constructor to create an empty list.

[hacker1024]

List.empty is fixed-size by default, which means the tear-off cannot be used in the way I describe.

[natebosch]

Should we consider deprecating and eventually removing the argument specifically, without removing the constructor?

There is risk that usages will get missed because of the tearoffs.

[lrhn]

We could remove the parameter of List when we release Dart 3.0, and keep the constructor with no argument creating an empty growable list.

It's not really necessary. The canonical way to create an empty growable list is []. That makes List() only really usable for tearoffs, and you can still just write ()=>[] and get the same effect. I'd prefer just dropping the constructor entirely.

[natebosch]

If it was zero effort for us I think I'd want to keep List.new for consistency with Map and Set (or I'd be fine dropping all 3 if it was zero effort for our community to migrate to using only literals). As is, I think I agree the inconsistency is not worth the effort to fix, given that the () => [] (or <T>() => <T>[]) function literal is a readable enough workaround.

[Lelelo1]

Yes please remove that parameter. It doesn't make sense to create an empty list you can't put anything in.

[lrhn]

@Lelelo1 I assume you refer to the growable parameter of List.empty.

It actually does make sense to create unmodifiable empty lists of a specific type. Some algorithms creates a new fixed-length list of a specific type, and if there are no elements to put into the list, it needs to be empty. It's not very common, but it happened often enough during the platform library null-safety migration that we added List.empty to help us.

The parameter I suggested removing above was the optional argument to the List constructor. Without that, the List constructor could be used to create an empty growable list, and its tear-off can be used as a constant function creating such. Currently, you simply cannot call the List constructor in null safe code, and it's scheduled to be removed in Dart 3.0 (when non-null-safe code stops working).

[anpol]

I was trying to implement Python-style "defaultdict" (a.k.a Perl-style autovivification) pattern, having hard time realizing why the following code does not compile:

  var dictOfMapsOfLists = <String, Map<String, List<int>>>{};
  dictOfMapsOfLists
      .putIfAbsent('foo', Map.new)  // OK
      .putIfAbsent('bar', List.new) // error: Member not found: 'new'.
      .addAll([42, 45, 47]);

Replacing List.new with () => [] would make the code compile, but it wouldn't make it readable.

Replacing List.new with List.empty would also make the code compile, leading to a runtime error.

Further comments:

1. The absence of List.new suggests that Map.new doesn't exist. That's not true.
2. The existence of List.empty suggests that Map.empty exists. That's not true.
3. The name of List.empty doesn't suggest that the result is an unmodifiable List by default. That's surprising.
4. List.empty() has the same result as List.unmodifiable(Iterable.empty()). That's redundant.

[lrhn]

List.empty exists because List.filled requires a second argument, even when the length is zero. That's what it should be compared to, not Map.new.

Also Map.new doesn't really need to exist. It does for historical reasons, but we could remove it. The canonical way to create a new map is the map literal.

We could add a List() constructor which always creates an empty growable list, but from a style perspective, we don't want people to use it. It would only be there for tearing off, which is not a strong enough use-case to warrant such a prominent position.

The canonical way to create empty lists is:

• growable: []
• fixed length: List.empty()
• dynamically chosen: List.empty(growable: b)

Providing a constructor tear-off for each of these is not a goal, a function expression like ()=><T>[] is perfectly adequate and acceptable.

Tearing off constructors is a fine use when they're there, but we generally don't add constructors just so they can be torn off.

And Map doesn't have the same distinction because it has no concept of "growable". It just has a legacy constructor that we haven't had a good enough reason to remove.

[anpol]

Well, that might have further explained why List.empty cannot be used instead of List.new.

That doesn't explain why the result of both List.filled and List.empty are unmodifiable by default, unlike the result of any other List constructor. No other collection class even provide a constructor with the growable parameter, relying on the mere existence of the Collection<T>.unmodifiable() helper instead.

Having compatibility concerns in mind, couldn't the following changes be made for consistency?

1. Re-introduce List.new() always returning a growable List.
2. Introduce a clearly named Collection<T>.unmodifiableEmpty() constructor for all collection types; implementation is => Self.unmodifiable(Self.new());
3. Deprecate List.empty(), replace with List.unmodifiableEmpty(), as defined above.
4. Deprecate List.filled(), replace with List.repeating(num, val) always returning a growable List.
5. Check that Collection<T>.unmodifiable() is optimized in a way that using the growable parameter is not necessary anymore.
6. Deprecate the growable parameter of all List constructors, suggest using .unmodifiable() instead.

[anpol]

we generally don't add constructors just so they can be torn off.

On the other hand, making collection classes share a common vocabulary would make the core library more compact, thus making the language easier to grasp and to teach. It must be the goal of a library design.

For now it looks like the constructor is absent for no reason, which is hard to explain.

---

And Map doesn't have the same distinction because it has no concept of "growable".

I'm sorry, but that looks like another issue I didn't quite realize at first.

  var x = List.of([1, 2, 3], growable: false);
  var y = List.unmodifiable([1, 2, 3]);
  var z = Map.unmodifiable({'foo': 3});

  for (var run in [
    () => x.add(4),     // Cannot add to a fixed-length list
    () => x[2] = 4,     // OK
    () => x.clear(),    // Cannot clear a fixed-length list
    () => y.add(4),     // Cannot add to an unmodifiable list
    () => y[2] = 4,     // Cannot modify an unmodifiable list
    () => y.clear(),    // Cannot clear an unmodifiable list
    () => z['foo'] = 3, // Cannot modify unmodifiable map
    () => z['bar'] = 4, // Cannot modify unmodifiable map
    () => z.clear(),    // Cannot modify unmodifiable map
  ]) {
    try {
      run();
      print('OK');
    } catch (e) {
      print(e);
    }
  }

So a non-growable List concept differs from an unmodifiable List in that its content is modifiable, but its length is not.

Can you explain why a separate concept of "growable" exists for List only, but it doesn't exist for Map? It's obviosly implementable for both of them. Does it worth the effort in either case? Did someone researched into or have a prior experience with "non-growable but modifiable" Lists in Dart or other programming languages?

[lrhn]

The non-growable/fixed-length list is really the array of Java or a similar fundamental allocated sequence of values in other languages. It's the type that most other data structures are based on.

A growable list is a mutable data structure, which performs re-allocations and moves references around. The native implementation is based on manipulative underlying fixed length lists.

Both sets and maps also use fixed length lists as part of their implementation.

The only thing Dart does a little differently is that it applied the full List interface to arrays, even if some of the operations won't work That was based on a wish to make things simple, by not having a large number of similar interfaces that users would have to choose between when writing their APIs.

[anpol]

Thank you very much for the details.

The only thing Dart does a little differently is that it applied the full List interface to arrays, even if some of the operations won't work

Not only does Dart apply List interface to arrays, but it also applies array-style "growable" concept to Lists, and that looks objectionable.

I was wrong supposing that Java doesn't have "non-growable" ArrayLists , expecting it only has an unmodifiableList() concept.

Surprisingy, Java has "non-growable yet modifiable" lists in two cases: returned by nCopies(n, v), and singletonList(v).

[lrhn]

Being growable is more of a List concept, so applying it to lists is reasonable. It's a non-growable array-like also implementing List that's different.

Java has the primitive array concept, which is fixed size chosen at allocation, and is the fundamental "allocate space for n elements of this type". And it has the data-structure List interface which is usually growable (except for some choice special-cases, as you've found). Same for C#, arrays (int[]) and lists IList<int>.

Dart tries to avoid having "primitive" types at all. It doesn't have unboxed integers, and even null has a class that it implements. All values are class instances. (But we backtraced on that in Dart 2 when it came to functions, and now records, which really are structural types.)

Dart also tries to avoid having too many different versions of interfaces. There is no FixedLengthList marker interface that a fixed length list could implement. Or it could have been a supertype of List without the length-changing members. But then anyone writing a method would have to think "should my argument type be FixedLengthList or List, and that wasn't considered worth the hassle. (Dart 1 was a very dynamic language, the fact that some operations could throw at runtime was not a worry at all.) We've stuck to that design, which means that we don't have any of the, potentially useful, EfficientLengthIterable, EfficientElementAtIterable, EfficientContainsIterable, FixedLengthList, or UnmodifiableList interfaces. There is one List. It has one useful supertype, Iterable. And that's that. (It can be questioned, but it's a somewhat consistently followed design philosophy.)

That's why the Dart "array" type is also considered a List, just a fixed-length one. With that concept in place, "some lists are fixed length", we can have other fixed-length lists. Typed-data lists are also array-like fixed-length and still implements List.

Fixed length lists are special among data-structures. You could have a "fixed-key-map" where you create an optimal hash for a fixed set of keys, and only allow you to change their values, but never add new keys (and it might even make sense for some JSON operations), but it hasn't been requested enough to have been a priority. A "fixed-length set" makes no sense, if it's not unmodifiable. (Unless it has an exchange operation which removes one element and adds another, which ... still makes no sense.)

Which means that the choice of collection types, and non-type-based variants of those, that we have today are there for a reason. Most reasons are still valid, but some of the constructors might not be needed any more. The Map and Set constructors don't really need to exist, not after we got the set literal, and removed the List constructor. Many of the Map "from..iterable.." constructors should just be removed, since we got {for (var x in xs) x.name: x} literals that are plain better.

All in all, there are no plans to add a List() constructor which doesn nothing that [] can't do, except being torn off. That's not enough reason to have it. Symmetry is nice, but I'd rather achieve that by removing than by adding.