Thursday, December 22, 2011

Lists and arrays in Dart

(This is Part 3 in a series about Dart. Check out Part 2, Function in Dart.)

Warning: We expect the Dart libraries to undergo potentially sweeping changes before Dart goes to alpha. This document is relevant as of 2011-12-22.

Intro

Dart is a "batteries included" effort to help app developers build modern web apps. An important "battery" is the bundled core Dart libraries, providing common and rich functionality. Dart is building a solution for large, complex web apps, and providing well tested, integrated, and common libraries is key to helping a web app developer be more productive out of the box.

The Collection libraries are a crucial set of APIs that Dart developers get for free. Much more than simple arrays and maps, the Collection library includes standard ways to filter, iterate, inspect, compose, and sort your data. This post specifically looks at List<E>, Dart's ordered, indexable collection of objects.

Aside: The Dart project is lucky to welcome Josh Bloch to the team, who will be leading the library design efforts. Expect some great things for the libraries and Dart!

Arrays are Lists

Perhaps the most common collection in nearly every programming language is the array, or ordered set of objects. Dart arrays are Lists, so look for List in the documentation. A Dart List will compile to a JavaScript array.

Fun fact: As of 2011-12-22, the word "array" does not appear in the Dart spec.

List basics

Dart supports List literals like JavaScript. A simple Dart list:

main() {
  var list = [1,2,3];
  print( list is List ); // true
}

Get the list's length, or number of elements inside of the list:

main() {
  var list = [1,2,3];
  print( list.length ); // 3
}

Access the second element in the list: (notice how Dart list indexes are 0 based, i.e. 0 is the first element, 1 is the second element, etc)

main() {
  var list = [1,2,3];
  print( list[1] ); // 2
}

If you try to reference an element that is outside the length of the list, you'll get an IndexOutOfRangeException.

main() {
  var list = [1,2,3];
  print( list[5] );  // Unhandled exception: IndexOutOfRangeException
}

Add an element to a list constructed from a list literal:

main() {
  List list = [1,2,3];
  list.add(4);
  print( list.length ); // 4
}

Now is a good time to point out that the add(object) method is optional. That is, not all implementations of List have to support it. I don't personally like optional methods, but this is where we stand as of 2011-12-22.

An example of a List that you can't add to is the fixed size List, as constructed by:

main() {
  var list = new List(3);
  list.add(4); // this throws an UnsupportedOperationException: Cannot add to a non-extendable array
               // exception thrown for Lists constructed with an initial size
}

Unfortunately, the docs right now don't clue you in that the new List(size) constructor returns a fixed size List, but follow bug 948 for the comment fix.

It's important to know that when you construct a fixed size List, that the List itself is allocated to that size and filled with nulls for the size of the List. For example:

main() {
  var list = new List(5); // [null,null,null,null,null]
  print(list[0]);  // null
}

Also important to know for JavaScript developers: Lists in Dart are not associative arrays. That is, the following code will NOT work in Dart:

main() {
  var list = new List(); // no initial size! aka EMPTY
  list[3] = 'hello'; // IndexOutOfRangeException
}

Remove an element from a list: (I know, I know, we're lacking a simple removeAt(index) function (see bug 947). See comment about Josh Bloch above and just hang tight :)

main() {
  List list = [1,2,3];
  list.removeRange(1, 1); // remove only the second element
  print( list.length ); // 2
}

To print the elements of a List, we need to add a map() function to eventually convert a List to a List<String> because Strings.join only takes a List<String>. The Dart libs are lacking a map function on collections (see bug  945).

List map(List list, converter(x)) {
  final List result = [];
  for (final x in list) {
    result.add(converter(x));
  }
  return result;
}

List<String> listToStrings(List list) {
  return map(list, (x) => x.toString());
}

main() {
  List list = [1,2,3];
  print( Strings.join( listToStrings(list), ',' )); // 1,2,3
}

Sorting

Sorting a List takes advantage of Dart's function support.

main() {
  var list = [4,1,2];
  list.sort(compare(a,b) {
    if (a == b) {
      return 0;
    } else if (a > b) {
      return 1;
    } else {
      return -1;
    }
  });
  // list is now 1,2,4
}

Iterating

Iterating over a List can be done in at least four ways. The standard, most familiar way is the for loop:

main() {
  var list = [4,1,2];
  for (var x = 0; x < list.length; x++) {
    print(x);
  }
}

There's a more terse way of using for if you don't need the current iteration index:

main() {
  var list = [4,1,2];
  for (final x in list) {
    print(x);
  }
}

The verbose way to say the above is to use a formal Iterator from the List:

main() {
  var list = [4,1,2];
  Iterator i = list.iterator();
  while (i.hasNext()) {
    print(i.next());
  }
}

And finally, if you just want to apply a function to each element of the List, use forEach:

main() {
  var list = [4,1,2];
  list.forEach(f(e) => print(e));
}

Filtering

The Collection interface, which List extends, provides a filter method, which returns a new collection with only the elements that satisfy a condition.

An example of filtering:

main() {
  var list = [4,1,2];
  var evens = list.filter(f(e) => e % 2 == 0);
  printList(evens); // 4,2
}

Of course, you don't need to inline the filtering function. Passing in a function also works:

isEven(x) => x % 2 == 0;

main() {
  var list = [4,1,2];
  var evens = list.filter(isEven);
  printList(evens);
}

Next steps

Check out the every(bool f(E element)) and some(bool f(E element)) methods to check if the List matches every condition or at least one condition, respectively.

Of course, please review the full Collection<E> docs and the List<E> docs.

Summary

Dart has Lists which are ordered sequences of objects. There is no class or interface called Array, though Lists act extremely similar to Arrays you might have encountered in other programming languages.

Dart Lists are not associative arrays like JavaScript, but Dart does have list literals for easy declaration.

The core Dart libraries will almost certainly undergo sweeping changes now that Josh Bloch has joined the team. For now, though, there's still a lot you can do with Dart's lists. As you work with the libraries, remember that Dart is in Technology Preview mode, and we really want to hear your feedback.

What do you need from the libraries? Let us know at the mailing list or please file an issue. Thanks!

Next steps

Check out Part 4: Maps and hashes in Dart.
Post a Comment

Disclaimer

I'm probably required to say that the views expressed in this blog are my own, and do not necessarily reflect those of my employer. Also, except as otherwise noted, the content of this page is licensed under the Creative Commons Attribution 3.0 License, and code samples are licensed under the BSD License.