Programming languages naturally come with a library of containers or collection types. They allow us to easily work with arbitrary number of elements, which is something all major languages care about. Unfortunately, it seems like there is not much writing on how to design such libraries. Even asking a few people that worked for a long time on collection libraries did not yield much of a structured approach to such a central element for our languages. The one major piece of writing we found is the Scala people describing their experience with bit rot and how they redesigned their collection implementation to avoid it.

There do not seem to be any concrete answers on what one should include in a collection library however. So, which types of collections are useful? Which ones are must haves, and which ones would be nice to have? What should the overall shape of the library be and how should collections be designed to work well together?

Trying to find answers to at least some of these questions, we started to look into the libraries of various languages to get a feeling of common design aspects and design dimensions. And the possible design space seems huge. Some languages have only a minimal set of standard collections, for instance, C and Lua. Languages such as Java and Scala have however large numbers of collections.

To weight the various options against each other, we chose to discuss the design dimensions we found in the context of exploratory programming. The discussion is part of the write-up below.

We will present this work in about a month at the PX/18 workshop in Nice, France.

Abstract

While an integral part of all programming languages, the design of collection libraries is rarely studied. This work briefly reviews the collection libraries of 14 languages to identify possible design dimensions. Some languages have surprisingly few but versatile collections, while others have large libraries with many specialized collections. Based on the identified design dimensions, we argue that a small collection library with only a sequence, a map, and a set type are a suitable choice to facilitate exploratory programming. Such a design minimizes the number of decisions programmers have to make when dealing with collections, and it improves discoverability of collection operations. We further discuss techniques that make their implementation practical from a performance perspective. Based on these arguments, we conclude that languages which aim to support exploratory programming should strive for small and versatile collection libraries.

  • Few Versatile vs. Many Specialized Collections: How to design a collection library for exploratory programming?
    S. Marr, B. Daloze; In Proceedings of Programming Experience Workshop, PX/18, p. 135–143, ACM, 2018.
  • Paper: HTML, PDF
  • DOI: 10.1145/3191697.3214334
  • BibTex: bibtex 
    @inproceedings{Marr:2018:COLL-PX,
  abstract = {While an integral part of all programming languages, the design of collection libraries is rarely studied. This work briefly reviews the collection libraries of 14 languages to identify possible design dimensions. Some languages have surprisingly few but versatile collections, while others have large libraries with many specialized collections. Based on the identified design dimensions, we argue that a small collection library with only a sequence, a map, and a set type are a suitable choice to facilitate exploratory programming. Such a design minimizes the number of decisions programmers have to make when dealing with collections, and it improves discoverability of collection operations. We further discuss techniques that make their implementation practical from a performance perspective. Based on these arguments, we conclude that languages which aim to support exploratory programming should strive for small and versatile collection libraries.},
  acceptancerate = {1.00},
  author = {Marr, Stefan and Daloze, Benoit},
  blog = {https://stefan-marr.de/2018/03/how-to-design-collection-libraries/},
  booktitle = {Proceedings of Programming Experience Workshop},
  day = {10},
  doi = {10.1145/3191697.3214334},
  html = {https://stefan-marr.de/papers/px-marr-daloze-few-versatile-vs-many-specialized-collections/},
  isbn = {978-1-4503-5513-1},
  keywords = {Analysis Collections Design Framework Implementation Library MeMyPublication Opinion Survey myown},
  month = apr,
  numpages = {9},
  pages = {135--143},
  pdf = {https://stefan-marr.de/downloads/px18-marr-daloze-few-versatile-vs-many-specialized-collections.pdf},
  publisher = {ACM},
  series = {PX/18},
  title = {{Few Versatile vs. Many Specialized Collections: How to design a collection library for exploratory programming?}},
  year = {2018},
  month_numeric = {4}
}

Slides