De-throning the List: Part SC4K
Tags: elm
Published: 2018-04-23 17:37:27

---
title: De-throning the List: Part SC4K
published: true
description: The API for List, Array and Set are different. Does that have to be the case?
tags: elm
---

In the [last post](https://dev.to/skinney/de-throning-the-list-part--44dl) we looked at how we could make `Array` more expressive. By which I mean we added a way for people to extend the data structure to support more use cases. But while third parties now can add missing functionality, there are certain functions which should be supported out of the box, both for performance and convenience reasons.

Elm has four built-in collection types: `List`, `Array`, `Dict` and `Set`. With the exception of `Dict`, these types look similar from a birds eye view. You can insert an item into the collection, get it back out, and even perform some task for every item stored. Of course, they do have different trade-offs which make them suitable for different situations.

The `List` is great when adding and retrieving items at the beginning (left side) of the collection. `Array` is great when you need fast access to any element, and `Set` is good when you need a sorted collection with no duplicates.

The API for these collections are different as well. Sometimes this makes sense, but not always. For instance, there is no `sort` function for `Set`, which is reasonable as `Set` is a sorted collection. However, there also isn't a `sort` function for `Array`, which means that you have to convert it to a `List` or a `Set` and then back again if you want it sorted.

Converting from one collection type to another is a costly operation. If you use an `Array` because it suits your use case most of the time, you don't want to convert to another collection just to perform that one operation.

Let's look at how we can improve the API of `List`, `Array` and `Set` to reduce the need for converting from one collection type to another to support the functionality you need.

## Differences which should remain

Certain operations aren't supported on a collection type with good reason. For instance, there is not `get` or `set` operation on `List` because the performance would be bad. If one need to `get` or `set` a random item in a collection, `Array` should be used. Likewise, `union`, `intersect` and `diff` should only be supported for `Set`. Here are some functions that are not supported by all three collection types, which I believe shouldn't be supported either:

`get`, `set`, `insert`, `remove`, `::` and `push` can only be supported efficiently by their respective collections. If you're in need of one of these functions, it's a tell-tale sign of which collection you should use. However, with the improvements I've mentioned in earlier posts, `Array` could support all of these functions efficiently, which is yet another reason as to why `Array` should be the default collection type.

`indexedMap` and `toIndexedList` make no sense for `Set`, as it doesn't operate by indexes and doesn't retain insertion order. `repeat` doesn't make much sense for `Set` either, as it cannot contain duplicates.

`union`, `intersect` and `diff` can only be efficiently implemented by `Set`.

`head` can be supported efficiently by the other collections, but the operation itself really only makes sense for `List`. `Array` would use `get 0`, and it isn't quite clear what `head` means in the case of `Sets`, is it the first/lowest/minimal element or the root/middle element?

`sort`, `sortBy` and `sortWith` doesn't make sense for `Set`, but `Array` should definitely get these functions.

`reverse` can be implemented efficiently for `Array`, but makes little sense for `Set`.

## Where we could bridge the gap

Below is a list of functions which can be easily supported across all three collections:

* singleton
* initialize
* range
* concat
* intersperse
* member
* map2, map3, map4, map5
* concatMap
* filterMap
* partition
* take
* drop
* unzip
* slice
* sum
* product
* maximum
* minimum
* all
* any
* scanl

While these functions could be supported across all three collections, does that mean they should? Since we're already messing about, let's ask ourselves if there are certain functions that shouldn't be in core to begin with.

`sum` and `product` are essentially shortcuts for `List.foldl (+) 0` and `List.foldl (*) 1`. Are those operations common enough to grant them dedicated functions in the core library? If we introduce `slice` for all three collections, do we need `take` and `drop`?

Do people actually use `map4` and `map5`? How about `scanl` and `unzip`? I mean, there probably are, but are those operations so common that one would expect to find them in core? Not that it necessarily does any harm, but there is something to be said of having a small, but powerful, package where you can read the entire documentation in a short sitting.

Anyway, here's a list of which functions I, personally, see no reason for having in core. I expect people will tell me that these functions definitely belong, but I think it would be nice to at least have the discussion.

* intersperse
* map4
* map5
* concatMap
* unzip
* sum
* product
* scanl
* take
* drop

## Finishing touches

Here are some minor things I think shouldn't be left out of a API renovation:

`List` and `Array` has a `length` function, `Set` has `size`. This is likely due to the fact that `Set` is a thin abstraction on top of `Dict` and so has just copied the name. I would rename `Set.size` to `Set.length` out of consistency if nothing else.

Now that I'm on the topic, since `Set` is  thin abstraction on top of `Dict`, maybe everything discussed up til this point applies to `Dict` as well?

`List` has `::` and `tail`. The analogous for `Array` is `push` and `pop`. `pop` is missing from the API, so I would add it.

I would add `find` for all three collections. `List` and `Set` already supports `member`, which is essentially `find` except that it returns a boolean instead of the value for which the predicate function returns true. It's a more useful function in general, and so if `member` should be a part of the API (which I believe it should) then `find` belongs as well.

For `Set` and `Dict` I would throw in `min` and `max` to retrieve the minimum/first and maximum/last element.

I think `Stack` is a better name than `List` and so would rename that type. It's a name that more clearly explains what that collection type is good at.

Finally, as mentioned in the previous post, I think `stoppableFoldl` and `stoppableFoldr`, or something with the same functionality but with better names, should be added to the API of `Array`. I think `Dict` and `Set` could be well served with that functionality as well.

## What do you think?

The goal I'm trying to reach is to make the `Array` type more general purpose, but when improving the `Array` API, it makes sense to look at the other collection types as well. This article lays out what I believe those APIs should look like.

First, I want to say that I'm not authority on what makes it into Elm. If I actually code up the suggestions in this article and submit it as a proposal, all of it could make it in, or none of it.

Second, all these suggestions are based on my own experience. What I need is your experience. Does these suggestions make sense, or am I off my rockers? Let me know in the discussion thread on the [Elm Discourse](https://discourse.elm-lang.org/t/de-throning-the-list/997/32).

## And now, for something quite different

So, is this the end of this series? Not quite. There's a summary left the be published, but that will have to wait until after we go over the top (you didn't think I'd forgot, did you?) in the [next post](https://dev.to/skinney/de-throning-the-list-part-boron-185), which is about the literal representation of `List` and `Array`.