Immutable collections and tools for TypeScript​

A new collection library for TypeScript? Aren't Array, Set, and Map good enough? What about immutable.js? Well, I understand you have a lot of questions my friend. Let me start by describing what Rimbu is all about.

Immutability: Create safer code​

When you start using TypeScript, you are taught it is better to use const where possible instead of let or var. Why is that? Well, mainly because, once you assign a value with const, you cannot change its value. If you want a new value from that value, you will need to write a new const and give it a new name:

const a = 5;
a += 1; // Compiler error!
const b = a + 1; // OK

However, this principle breaks down when we use referenced values like object or Array. When we assign such a value to a const, we cannot make it null. But we can change its contents:

const arr = [1, 2, 3];
arr.length = 0; // this is fine
console.log(arr);
// => []

You see that we can certainly change the value even though we use const. This breaks the whole story about not being able to change const values!

This is where immutable collections and objects come in to save the day. An immutable object, by definition, cannot be changed. Once it's created, its values will always be the same, no matter what you do to it. Combined with const, we have back our sacred principle of not being able to change assigned values.

But, I hear you say, what's the use? How can we add values to immutable collections? Well, it simply the same as the story of adding 1 to a const number:

import { List } from '@rimbu/collections';

const list1 = List.of(1, 2, 3);
const list2 = list1.append(4);

console.log(list2.toString());
// => List(1, 2, 3, 4);
console.log(list1.toString());
// => List(1, 2, 3);

In this example you can clearly see that list2 is a new list with other values than list1. Even though we added a value to list1, its contents did not change. This is exactly the benefit of immutability, you never have to worry about values having changed while you were not looking.

Smart and strong type safety​

Rimbu goes to great lenghts to ensure that the compiler will 'understand' what you are trying to do, but still prevent you from making obvious mistakes. For example, imagine the following:

import { List } from '@rimbu/collection';
const list1 = List.of(1, 2, 3);
// type of list1: List.NonEmpty<number>
const list2 = list1.append('a'); // error: string is not assignable to number
const list3 = list1.extendType<number | string>().append('a');
// type of list3: List.NonEmpty<number | string>

The compiler will rightly prevent you from appending a string to a list of numbers. However, you can still do that without needing to cast using the extendType method. Furthermore, you see that the lists get type List.NonEmpty instead of List. All Rimbu collections have this type information to indicate whether the compiler can know at compile time that the collection has at least one value. This allows us to write code that by definition rejects empty collections, and saves us from having to write checks for empty collections and thinking about how to handle such situations. In particular, it saves us from writing boring tests.

These are just small examples from a plethora of built-in smartness that the Rimbu collections possess.

Performance: Rimbu collections designed for performance​

Because immutable collections are often described as 'copying' data, they are often assumed to be slow. However, there is a principle called 'persistence', which allows them to actually be really fast. Persistance actually means memory sharing. Rimbu immutable collections will share memory as much as possible as long as no changes need to be made. The collections only duplicates parts of shared data that are modified. The rest of the data remains shared. This is because the collections keep their data in block-like structures, comparable to blocks on hard-drives. If some collection uses 50 blocks of data, and one value is changed, chances are that only 2 or 3 blocks need to be copied and changed, while the rest stays the same and shared. In some cases, persistent collections can be faster than mutable collections. For example, reversing a List of N elements in Rimbu has complexity O(logM(N)) where M is usually 32, so it is really fast for large collections as well. For a mutable array, the complexity is O(N), and therefore much slower. A similar story goes for memory complexity, however I will probably cover this topic some other time.

Simplicity​

Rimbu is mostly about giving the programmer new powerful tools to write safe and effective programs that are simple. For example, it avoids using advanced functional programming concepts like Monads, because they make code harder to understand and read.

This is why you will not find an Option or Maybe type (which are monads). Still, Rimbu provides nearly the same power in all methods that can fail:

import { List, err } from '@rimbu/core';

const list = List.of(1, 2, 3);

const v1 = list.getAtIndex(1);
// type of v1: number | undefined

const v2 = list.getAtIndex(1, 'not found');
// type of v2: number | 'not found'

const v3 = list.getAtIndex(1, -1); // return -1 if not found
// type of v3: number

const v4 = list.getAtIndex(1, () => 'lazy failure');
// type of v4: number | 'lazy failure'

// err is a function that throws an error when invoked
const v5 = list.getAtIndex(1, err);
// type of v5: number

In this way it is not needed to write things like list.getOption(..).map(..).getOrElse(..) or if (list.get(1) === undefined) throw Error()

But still, what about immmutable.js?​

Of course we already have a very nice JavaScript immutable collection library for years, called immutable.js. To be honost, I've never used it myself in projects, but I have read their documentation. The first thing that strikes me, in comparison to Rimbu, is that immutable.js is focused firstly on JavaScript and added types later on. Secondly, it has a few basic collections, like Maps and Sets, but Rimbu has many more (up to Graphs). Finally, it has Records to define immutable objects. However, with TypeScript, we can use the compiler to supply deep readonly types that prevent modification of plain objects. In this way this is a very lightweight and easier to use approach.

What's to come?​

In the coming time, I want to write much more documentation, and I hope to receive feedback on the current state of the library from other users. If there are requests for other types of collections, I would be willing to implement them and add them to the library.

In my Scala days, I became very interested in immutable collections, especially Scala's Vector. I was watching all kinds of YouTube videos from conferences that discussed how it works, and why it offers reasonably fast random access (debatably called effectively constant time). At the same time, I discovered that the Vector did not have an insert or remove method, and I wondered why. I started investigating how the data structure works, and read papers with proposals on how to improve the structure to allow random insertion. I also started getting ideas on how it could be done differently and started implementing my own structure.

This was going slowly but I was progressing. And while I was doing that, I also found ways to have better typed methods for collections in Scala. I thought I might as well create a whole collection library instead of just one collection implementation. I learned a lot from this effort about immutable data structures and creating strict but useful types. However, after some time, I realized that Scala, while having a great compiler, was holding me back in writing the code I wanted to write. Also, it seemed the community was getting split (due to a complete rewrite of Scala), and its popularity seemed to go down. In the meantime, Scala does have a new Vector implementation with the insert and remove methods. I actually discovered this quite recently. However, I found the documentation of the structure lacking so I cannot compare it to my approach.

Since I was now using TypeScript at work, it seemed an interesting exercise to me to see if I could better write down my ideas in this language. It turned out that this was indeed the case. And stil, I could create quite rich interfaces for the collection methods. This led me to abandon the Scala effort, and fully focus on the TypeScript library (I basically ported/rewrote the Scala code to TypeScript). And now, I have (finally) released the Rimbu library.

There are many things still to be done, but I am satisfied with the library so far. I hope developers will find it useful for their own projects, and am hopeful to hear what they think of it. I hope to find time to extensively document the data structure behind Rimbu's List in the near future. I find it quite a remarkable data structure myself. I hope to write some blogs as well on interesting use cases I found for the various collections. Stay tuned!

Programming has, from a young age, been one of my passions. I remember starting in the early days in Basic. It felt like magic, being able to write infinitely many programs to do all kinds of fun and useful things. As I grew better at it, I remember my programs began to get larger as well. Soon, I discovered that the limited support for subroutines (primitive procedures) quickly made a mess of my programs, and I lost oversight.

Then I moved on to Turbo Pascal. Again, I was really happy with the way I could use modules, functions and procedures to better structure my code, so I could scale my programs up without everything becoming one big mess, but it still had its limits. It wasn't until university that I really became aware of the importance of structured programming to keep complexity at bay. I became really interested (as many I guess) in pure functional programming, and actually did my Master's Degree in this topic. Composing functions and having no mutability were things that really struck me as being game changers for scaling programs.

Then, after university, reality kicked in: almost no company was (is?) using pure functional programming. So I went back to Java, C#, etc. I did spend a lot of my free time using Scala, which I still think has a great mixture of different paradigms, including immutable collections. But Scala, unfortunately, was also not really used inside the company.

Then the projects I worked on for my company led me to learn JavaScript, and later TypeScript. It was not love at first sight, but TypeScript, being a quickly evolving language with unique takes on types and soundness, did quickly resonate with me. It's far, very far, from perfect, but in return it is extremely expressive, especially concerning types. The sole support of union types makes any other language that doesn't have that feature feel like a major step back.

So after many years, programming is still my passion. And with TypeScript I am able to express most of my needs, even though it also often requires work-arounds or tricks that slow the compiler down quite a bit. I hope the language will continue to evolve and thrive, but especially improve. I like the fact that there are new developments like NativeScript to take the language out of the JavaScript sandbox. Unfortunately, NativeScript had to drop support for union types, which makes it a no go for me. I am really excited about Deno, a follow-up of Node built on Rust, and hope it will grow.

Did I expect TypeScript to be my go-to language a few years back? Definitely no. But right now I think it is the best language for me to write what I want to write, like, for example, the Rimbu Immutable Collections library.