Lean Iterable<E> - allow iterating without support for 30 methods

[passsy]

Iterable<E> defines 30 methods. That's too much because all an Iterable should do is to provide an Iterator. All other functions are only using the Iterator and are therefore not required to define an Iterable.

Additionally, Iterable can't be extended with new convenience methods. Every additional method breaks 3rd party libraries implementing Iterable<E>.

// Dart 2.1 Iterable<E> API
castFrom<S, T>(Iterable<S> source) → Iterable<T>
iterator → Iterator<E>
cast<R>() → Iterable<R>
followedBy(Iterable<E> other) → Iterable<E>
map<T>(T f(E e)) → Iterable<T>
where(bool test(E element)) → Iterable<E>
whereType<T>() → Iterable<T>
expand<T>(Iterable<T> f(E element)) → Iterable<T>
contains(Object element) → bool
forEach(void f(E element)) → void
reduce(E combine(E value, E element)) → E
fold<T>(T initialValue, T combine(T previousValue, E element)) → T
every(bool test(E element)) → bool
join([String separator = ""]) → String
any(bool test(E element)) → bool
toList({bool growable: true}) → List<E>
toSet() → Set<E>
length → int
isEmpty → bool
isNotEmpty → bool
take(int count) → Iterable<E>
takeWhile(bool test(E value)) → Iterable<E>
skip(int count) → Iterable<E>
skipWhile(bool test(E value)) → Iterable<E>
first → E
last → E
single → E
firstWhere(bool test(E element), {E orElse()}) → E
lastWhere(bool test(E element), {E orElse()}) → E
singleWhere(bool test(E element), {E orElse()}) → E
elementAt(int index) → E

Goal

Without those 30 methods it would be much easier for 3rd party libraries like kt.dart or built_collection to implement Iterable<T> allowing users to use custom collections in for loops. It is currently not or hardly possible because of many naming clashes.

Currently kt.dart users have to use the property iter to actually iterate over collections with for loops.

// error: The type 'KtList<int>' used in the 'for' loop must implement Iterable.
for(final i in listOf(1, 2, 3)) {
  print(i);
}

// .iter workaround
for(final i in listOf(1, 2, 3).iter) {
  print(i);
}

Solution A: Extension methods

Converting all methods to extension methods dart-lang/language#40 would be a major step forward. It would cleanup the Iterable class and removes the need for IterableMixin. This approach would also be future proof allowing method additions without requiring 3rd party libraries to adopt the new methods.

The naming clashes most likely wouldn't go away. It depends on how extensions will be imported which got discussed in dart-lang/language#41.

Solution B:

For backwards compatability Dart could provide a new class BareIterable which works in for loops, like Iterable today. All it does is providing the Iterator.

The existing Iterable class could even extend BareIterable<E>, keeping everything as it is.

abstract class BareIterable<E> {
  Iterator<E> get iterator;
}

abstract class Iterable<E> extends BareIterable<E> {
  Iterable<R> cast<R>() => Iterable.castFrom<E, R>(this);
  Iterable<T> map<T>(T f(E e)) => new MappedIterable<E, T>(this, f);
  // ... many more
}

3rd party collection libraries are then able to implement BareIterable<E> without implementing 30 more methods.

[munificent]

That's too much because all an Iterable should do is to provide an Iterator.

I'm not sure what justifies the should in that sentence. Users do use Iterable as a type in their APIs. If you have a method that accepts an Iterable, it's useful to be able to do lots of things with the object that you get, and the rich method set on Iterable enables that.

An implementer of Iterable is not burdened with manually implementing all of those. They can simply mixin IterableMixin and they get that behavior for free after defining iterator.

Additionally, Iterable can't be extended with new convenience methods.

Yes, this is generally a problem with interfaces in Dart and with classes in general. The lack of overloading and non-virtual methods makes basically every base class hard to change.

Without those 30 methods it would be much easier for 3rd party libraries like kt.dart or built_collection to implement Iterable<T> allowing users to use custom collections in for loops.

Sure, they could use them in for loops, but they couldn't do any of the other things users expect to be able to do with an Iterable. "Iterable" isn't just "the thing you can for over", it's a general purpose collection type for any sequence of values and it exposes as much useful functionality as it can.

Converting all methods to extension methods dart-lang/language#40 would be a major step forward. It would cleanup the Iterable class and removes the need for IterableMixin. This approach would also be future proof allowing method additions without requiring 3rd party libraries to adopt the new methods.

This would be nice, but I don't think we could reasonably do this in a non-breaking way. We don't have a time machine, and Iterable is what it is. (Many people on the Dart team did push for extension methods way back before Dart 1.0 specifically because it would have let us design the core libraries around them, but it didn't happen.)

I'm not sure what's actionable about this request. Users frequently call the many methods on Iterable, so we can't just take them away.

[kasperpeulen]

This would be nice, but I don't think we could reasonably do this in a non-breaking way. We don't have a time machine, and Iterable is what it is. (Many people on the Dart team did push for extension methods way back before Dart 1.0 specifically because it would have let us design the core libraries around them, but it didn't happen.

What would break if you implement all those methods as extension methods?

[munificent]

What would break if you implement all those methods as extension methods?

This depends a lot on the specific details of extension methods, which I think aren't pinned down yet. But, in general, it would probably move where the methods appear in the resolution order.

Today, you'd write something like:

abstract class Iterable<E> {
  bool get isEmpty;

  Iterator<E> get iterator;
}

abstract class IterableBase<E> implements Iterable<E> {
  bool get isEmpty => iterator.moveNext();

  Iterator<E> get iterator;
}

/// Special "collection" that always contains a single value.
class BoxIterable<E> extends IterableBase {
  final E _value;

  bool get isEmpty => false; // Always contains one item.

  Iterator<E> get iterator => [_value].iterator;
}

main() {
  Iterable<int> iterable = BoxIterable(123);
  iterable.isEmpty; // <--
}

On the last marked line, that's resolved like:

1. Look up isEmpty on the static type of the receiver, Iterable.
2. Find the abstract getter, so we know this is an instance member.
3. Compile it to a virtual call to that instance method.
4. At runtime, the object is a BoxIterable.
5. Look up isEmpty on that class.
6. Execute bool get isEmpty => false.

If you change isEmpty it to an extension method:

abstract class Iterable<E> {
  Iterator<E> get iterator;
}

extension IterableExtensions<E> on Iterable<E> {
  bool get isEmpty => iterator.moveNext();
}

/// Special "collection" that always contains a single value.
class BoxIterable<E> implements Iterable {
  final E _value;

  bool get isEmpty => false; // Always contains one item.

  Iterator<E> get iterator => [_value].iterator;
}

main() {
  Iterable<int> iterable = BoxIterable(123);
  iterable.isEmpty; // <--
}

Now the resolution, I think, looks something like:

1. Look up isEmpty on the static type of the receiver, Iterable.
2. It's not an instance method, so look for an extension method.
3. Find it on IterableExtensions<E>.
4. Compile a static call to that extension method.
5. At runtime, execute bool get isEmpty => iterator.moveNext().

So now you're calling a different method at runtime. In the example here, aside from wasting a little time and memory, the difference doesn't matter. But in real code, it very well could.

[lrhn]

I agree with Bob that it's probably not feasible to change Iterable now.

If we add static extension methods, with the semantics Bob was using (and which are the most likely ones to pick), then changing existing methods to extension methods will, as described, make them non-virtual. That is a significant change. Existing subclasses will keep compiling, but their specialized methods will no longer be called unless the static type at the invocation point is the subclass.
For example Set.last would be linear in time in the default implementation, even though L:inkedHashSet can do it more effectively.

[lrhn]

We now have extension methods.
We do not plan to change the Iterable interface. Removing methods is too breaking. Adding methods is too breaking until we get interface default methods. All in all, we are not going to address this issue.