Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Collection higher order functions should expose element index #5245

Closed
DartBot opened this Issue Sep 18, 2012 · 19 comments

Comments

Projects
None yet
@DartBot
Copy link

commented Sep 18, 2012

This issue was originally filed by joubert.nel...@gmail.com


What steps will reproduce the problem?

  1. every, filter, forEach, map, reduce, some all invoke functions to which the relevant element is passed, but not its index in the collection. http://api.dartlang.org/docs/continuous/dart_core/Collection.html
  2. Knowing the index of the element is often very useful.
  3. For example, in JavaScript, the .forEach method on Array passes in the index, the element, and the array to the callback function. per.mozilla.org/en-US/docs/JavaScript/Reference/Global_Objects/Array/forEach
  4. For example, in Go, the "range" clause in a "for" loop can yield the element's index. http://golang.org/doc/effective_go.html#for

What is the expected output? What do you see instead?

  • Callback invocation should include the element's index in the collection.
  • Only the element is passed as argument to the callback.

What version of the product are you using? On what operating system?

  • Dart SDK version 12439
  • OS X Mountain Lion

Please provide any additional information below.

@sethladd

This comment has been minimized.

Copy link
Member

commented Sep 19, 2012

@alan-knight

This comment has been minimized.

Copy link
Member

commented Oct 26, 2012

I'd like to see this as well. Or, more generally, I'd like to be able to iterate more polymorphically between Maps, Lists, and other collections. It's useful to be able to iterate over an indexable collection as if it were a map whose keys were consecutive integers. And it's also useful to be able to iterate over just the values of a Map. For example, it's useful to be able to do aMap.map() where the result is a new Map which has the same keys, but whose values have been transformed.

My suggestion would be to have two different iteration methods, one of which supplies a key, and one which supplies just the value. For something like a Set, where the key doesn't make sense, we can provide only the one variation. For map() I don't see as much use for a variation that would provide the keys/indices.

How far this might be extended is an interesting question. For example, filter(). That might be a useful operation on a Map, but its semantics would presumably be that you have only the key/value pairs where the value satisfies the predicate. On a list, filtering alters which index corresponds to which value, so the semantics aren't as symmetrical. So it might or might not be reasonable to have that operation available for both.

It would also be nice to have symmetrical operations between collections and strings.

@DartBot

This comment has been minimized.

Copy link
Author

commented Nov 30, 2012

This comment was originally written by beatga...@gmail.com


I think it also makes sense to use the same for Maps. This could be done by changing the definition of Map to extend Collection. This would change the order of key/value -> value/key in iteration functions, but I think this is acceptable to make dealing with collections in general easier.

For example, if a library just wants to get the data out, regardless of the way it's indexed, then it doesn't have to know if it's a map or a list, it would just work.

I'd prefer something closer to Go syntax with iteration, but since Dart doesn't have multiple returns, this would make things inconsistent.

@dgrove

This comment has been minimized.

Copy link
Member

commented Jan 11, 2013

Removed Library-Collections label.
Added Library-Collection label.

@lrhn

This comment has been minimized.

Copy link
Member

commented Jul 18, 2014

We have no current plan to add extra arguments to the iterable functions.

JavaScript allows calling a function with more arguments than it expects, which makes it reasonable to pass three arguments every time, even if you only need one or two of them. Users can write foo.forEach(function(a) { ... }) without worrying about the extra arguments. In Dart, they would have to write foo.forEach((a,x,y) { ... }) even if they only need the "a".

You can iterate the keys and values of a map independently, and you can iterate a list with indices by using list.asMap().forEach((index,value) { ... }).


Added NotPlanned label.

@DanTup

This comment has been minimized.

Copy link
Member

commented May 8, 2015

In Dart, they would have to write foo.forEach((a,x,y) { ... }) even if they only need the "a".

Is this not solvable? A colleague showed me today that TypeScript supports this fine. The forEach function expects a function that has optional parameters in its definition. TypeScript allows passing a function that is declared without arguments that are marked as optional in the function signature.

@lrhn

This comment has been minimized.

Copy link
Member

commented May 8, 2015

Typescript is Javascript, and therefore has the ability to call functions with more (or fewer) arguments than the function has parameters. Dart doesn't do that - and doesn't really want to do it because it's a great way to hide bugs.

@DanTup

This comment has been minimized.

Copy link
Member

commented May 8, 2015

I may be misunderstanding; but doesn't Dart already support this with optional parameters? TypeScript also does not let you pass more/less arguments to a function than it declares (unless they're marked as optional).

@lrhn

This comment has been minimized.

Copy link
Member

commented May 9, 2015

Optional parameters work in the opposite direction, they allow you to call a function with fewer arguments than it can maximally accept (and only when it's prepared for it). What we need here is to call a function with more arguments than it accepts, and then ignore the overflow. We can't do that with optional parameters. It's a property of the call, not of the function - which is the entire point of this problem: We want to be able to pass a unary function to forEach and have it work.
If we can pass a unary function and a binary function, and both gets called, then the function call must distinguish between the two functions and call them differently.

@DanTup

This comment has been minimized.

Copy link
Member

commented May 9, 2015

Sorry, I think I see the issue now. In TypeScript, it only needs to pass at "compile time", but I presume your rule is enforced at runtime (and I agree, removing that wouldn't be good).

That said (and I'm just clutching at straws here); couldn't the runtime part be handled with typedefs and is? (eg. like shown here -> http://stackoverflow.com/a/25961382/25124)

@lrhn

This comment has been minimized.

Copy link
Member

commented May 9, 2015

Yes, it could be handled by manually type-testing the function, and passing as many arguments as possible:
  if (action is TernaryFunction) action(v, i, this);
  else if (action is UnaryFunction) action(v, i));
  else action(v);
It's not very efficient (but I guess if we wanted it to be, we could add some optimized internal way to figure out the arity of a function), and it means you cannot type the argument of forEach more precisely than "Function".

All in all, I'd rather not complicate Iterable.forEach. Every time you have a function that has multiple "modes", you also get extra overhead from the dispatch logic.

@DanTup

This comment has been minimized.

Copy link
Member

commented May 10, 2015

and it means you cannot type the argument of forEach more precisely than "Function"

TypeScript handles this with the optional types marked on the definition of the function that needs to be passed. (Eg. it's valid to pass a function that takes one arg as an paramter that is a function that has only one manadatory arg, but two optional args). However, I don't know whether it's easy (or even possible) with how Dart works.

I understand the desire to want to keep things simple, but this does seem like nice functionality that many other languages and seems to match with the goals of Dart - converting to Maps and/or keeping our own counters doesn't feel like good code to write.

Every time you have a function that has multiple "modes", you also get extra overhead from the dispatch logic.

Sure; but I suspect the overhead of us doing asMap() is greater (both in terms of performance and mentally)! ;)

Obviously; I'm biased, because I'd like this feature and I don't have to make it work. I respect that you're in a far better position to understand the implications/complications; I was just curious when I was shown the TypeScript version and asked why you didn't have it.

There's always another option, but I suspect you'll like this even less:

https://msdn.microsoft.com/en-us/library/ee370378.aspx - F# List.map
https://msdn.microsoft.com/en-us/library/ee353425.aspx - F# List.mapi

F# just has an additional method (ending with an i) that takes a function that receives the index. It explodes the number of functions; but it's a simple and clear way to achieve it without sacrificing any typing and/or adding any overhead.

@lrhn

This comment has been minimized.

Copy link
Member

commented May 10, 2015

The fact that it works in TypeScript pretty much depends on TypeScript being JavaScript. JavaScript functions don't really have required parameters, and they accept any number of optional parameters. It is as if all functions were typed as "typedef function([p1, p2, p3, p4, .... , p1000000, ....])". When you declare a function, you just state the expected parameters., but you can always be called with fewer or more.

The Dart type system isn't that lenient.
In Dart, if a function has one parameter, then you can't call it with two or three, so a function of type (int->int) is not a subtype of (int,[int,int])->int - it has to actually be written to accept two optional parameters for that to be the case.
In order to say that forEach takes a function of one, two or three arguments, we need union types, which could be something like:
   forEach((Unary<E>|Binary<E>|Ternary<E>) action);

The asMap transformation is intended to be light-weight, both implementation-wise and conceptually (it's a thin wrapper around the list that makes it look like a map), but it might not be as clear as it should. I do recommend using asMap(), but Map doesn't have a map method (ironically, but it would probably be confusion), so it only works for forEach.

I could also accept having other map variants, but we don't plan on extending Iterable at this point - there are too many implementations of it out there that would be invalidated. Maybe if we get extension methods, but I fear that extension methods are not a good match for a language like Dart.

What we could also do is to have helper methods and wrappers:

  Iterable<Pair<E, int>> withIndex<E>(Iterable<E> iterable)

or for wrapping the called function:

  typedef Unary(x);
  Unary countCalls(action(argument, index)) {
    int i = 0;
    return (v) => action(v, i++);
  }

@baseten

This comment has been minimized.

Copy link

commented Nov 22, 2018

Not having this functionality makes operations involving multiple lists very cumbersome, when data at the same index is related. Unless there is some functionality I'm unaware of, you have to resort to a basic for loop, or create a List of matching length filled with indices and use the higher order functions over that.

I understand that from a language point of view overriding the basic methods to allow for different parameter lengths may be impossible. But could we not have additional methods like mapWithIndex, etc. Or, if possible, something like ruby does where it exposes an each_with_index method, which returns an enumerator.

@lrhn

This comment has been minimized.

Copy link
Member

commented Nov 22, 2018

With higher-order generic functions, we could add helpers like:

R Function(T) withCounter<R,T>(R Function(T, int) action, {int start = 0}) => 
    (T value) => action(value, start++);

Then you could do:

listOfString.forEach(withCounter((String x, int index) => "$string#$index"));

Helpers like that would fit well in package:collection.

Also, you can already do something similar for lists by going through asMap:

listOfString.asMap().entries.map((entry) => "${entry.value}#${entry.key}");

It doesn't work for general iterables, but assigning an index to those is kind-of speculative.

@kmillikin

This comment has been minimized.

Copy link
Member

commented Nov 22, 2018

You can also have a function that closes over some state like:

  int index = 0;
  ordinals.map((ordinal) {
    return 'On the ${ordinal} day of Christmas '
        'my true love gave to me ${gifts[index++]}.';
  }).forEach(print);
@lukepighetti

This comment has been minimized.

Copy link

commented Dec 13, 2018

Why was this issue closed?

Lets say you have a list of doubles and you want to create a list of booleans related to if the previous value was bigger or smaller.

With index available

final values = [1,2,3,2,1];
final isUp = values.map((val, i)=>val > values[i-1]);

Without

final values = [1,2,3,2,1];

List<bool> isUp = [];

for(var i of values){
  isUp.add(values[i] > values[i-1]);
}

Except that doesn't work because we don't have "of" in for loops. So we have to do this.

final values = [1,2,3,2,1];

List<bool> isUp = [];

for(i=0; i<values.length; i++){
  isUp.add(values[i] > values[i-1]);
}

And while this may seem like a small inconvenience, I have personally found that robust list methods make for incredibly clean and happy developer experience and are used day in and day out.

@lrhn

This comment has been minimized.

Copy link
Member

commented Dec 14, 2018

The issue was closed because we are not planning to change the existing APIs.

We could add more methods, but even that is a breaking change given how many classes already implement List, so unless we get interface default methods, we will still not change the List API for a feature like this.
If we get something like static extension methods, then anyone can add the functions if they want to, and it would again be something we'd put into package:collection.

As for the examples, well, they all crash when reading values[-1]. Which I guess shows why it's so important to have helpful APIs :)

The indices of a list are available, indirectly.
You can write:

for (var i in values.asMap().keys.skip(1)) {
  isUp.add(values[i] > values[i - 1]);
}

The discoverability (and readability) is pretty low, I'll admit.

I'm sure there is some Rx function that does what you want here. Again, the best chance of getting such functions would be extension methods or extension types.

@alecorsino

This comment has been minimized.

Copy link

commented Apr 4, 2019

Are you planning on adding method overloading that could add the above functionality to support having the index passed down to the forEach function? Being a Class oriented language this kinda would make sense to have method overloading. Dart seems, to me, is trying to be declarative only on the surface but we have to do lots of imperative programming.
How cheap is to convert to a Map with asMap?

This issue was closed.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.