Positional Lists in TypeScript

Deal with Lists without dealing with indexes

Photo by Brandon Mowinkel on Unsplash

Lists are data structures that save a sequence of items in order. Because of this we can work with indexes and modify them to get items with an offset to some index. This is great, but it can lead to code that modifies a lot of integers just to get and set items in the list on a certain position. In this article we look to positional lists, a kind of list that abstracts the concept of indexes and allows us to reason with just the concept of previous and next items.

Positional lists are lists that store items in a Position container. Based on this container you can retrieve the previous and next item(s) from the list without dealing with indexes (however indexes still are an option to get a position). This can help to create more elegant code because we abstract the concept of ‘the next item is at index + 1’ into the data structure. So no more variables like currentIndex and indexLastProcessedItem. It also allows us to easier work with circular data structures because the outside world isn’t anymore making assumptions about indexes.

The Position container

Part of the interface for a PositionalList

The positional list

Positional lists are a lot like normal lists, but there are some things to consider:

• Every value from the list gets returned inside a Position container
• The lists has before and after methods that return a Position based on another Position
• Removal happens by Position, not by index
• The backing data structure can be anything, every type of list is possible but arrays, circular buffers and indexed trees are also possibilities

Based on this information we can define an interface for the methods that a positional lists has to implement to actually work as a positional list. Of course it is possible (and very common) to add more methods that make the positional list more powerful and flexible.

The outline of a positional list

Note that we can still use our positional list as an regular list with the help of the elementAt, first and last methods to get a Position by an index and use it with the other methods.

Implementation with a double linked list

The easiest and most common way to implement a positional lists is with a double linked list. This because in a double linked lists it is simple to get the previous and next nodes of a node. It also already implements every single feature we listed above, so it requires only small changes to adopt to the PositionalList interface. A possible implementation can be found below:

Positional list implementation based on a double linked lists

The main ‘trick’ here is to have the Node interface extends the Position interface and up- and down-cast when passing nodes in and out of the list. The outside world only knows about positions, we inside the list know about nodes with previous and next items.

Seeing this implementation one could wonder why the before and after methods are on the list and not on the position. Surely it would be more convenient if we could do myPosition.before().before() instead of having to reference the list every time? The answer has two parts to it:

The first is abstraction and responsibilities. That the previous and next nodes are part of the position is something we with knowledge of the positional list know, but the outside system shouldn’t. They only thing they know is that there is something like a previous and next item in the collection, where and how that is stored is none of their business. A collection manages items and an item is just an item.

The half of the answer is that you don’t have to use a double linked list as a backing data structure for your positional list. A single linked list is also a valid option to us for an implementation and then you don’t have the handy previous property on your nodes. And then we are still considering a safe option close the double linked list. Let's take a look at another implementation that uses an array for storing the actual items:

Other implementations

A positional list can also be implemented with an array. For this we keep the array inside our PostionalList and all the methods modify and query this array. Here we see why it is better to keep before and after on the list, as they have easy access to the data variable. In this implementation we still have a Node interface, but now it stores the index as additional hidden data instead of storing the previous and next nodes. The full implementation can be found here.

Part of a positional list implementation based on an array

Here we see that in a language with dynamic resizing arrays (like JavaScript) a positional lists is actually shorter to implement with an array then with the more traditional double linked list. In for example Java or C# you would have to use an ArrayList with automatic resizing to get the same result.

Functional programming and positional lists

The definitions and implementations I have shown you so far have all been very basic and traditional OOP to keep things as simple as possible. But in the real word almost everybody is getting some functional programming into their code base, especially when modifying collections. Implementing function as filter and map is totally possible for a positional list, but there are some gotchas. Let’s start of by extending our PositionalList interface to add definitions for some of those functional goodies:

Interface for a positional lists that works with functional programming

As you see we don’t use positions for the items inside the map, filter and bind function. This is because we are not supposed to care about positions in those functions. the function we pass to map should just turn a T into an U without considering anything else then the value of that T.

map for a positional list, filter and bind will follow a similar pattern

Now we are starting to introduce methods that create new positional lists we should really start thinking about one issue: what if we pass a position to before or after that doesn’t belong to that list? In our previous implementation it would either work, produce nonsense or return null. We can add a check for this by putting a reference to the lists on the position and checking if that reference equals this before we consider a position valid.

Partial implementation of an isValid check in the positional list

Conclusion

In this article dived into one of the lesser used list variants, the positional lists. This feels a bit like a shame because positional lists are actually quite cool and powerful. Let me know what you think about them!

Want to read more about functional programming with TypeScript? I’m writing a series on the extended functor family in TypeScript, you can read the first two parts here:

Contravariant Functors in TypeScript

Bifunctors in TypeScript