Contribute to Open Source: complete process step by step

Open source is awesome! That's why I decided to contribute to Effect by adding a new data structure: a Trie.

I documented all the steps from the initial idea to the final implementation 🚶

This is my process step by step on how to contribute to open source 👇

---

Tech stack

• Javascript: implementing a data structure requires a solid understanding of how the language works. Back to the basics of javascript 💁🏼‍♂️
• Typescript: the language is javascript, but the types should also be there for the end user
• Effect: not anymore just the API, but reading and understanding the internal implementation

Setup

First things first: make sure my contribution is in the scope of the project 🤔

I asked on the Effect Discord channel if my idea of adding a Trie works. I made sure to understand all the requirements before starting my research for the implementation.

I had various experiences already with Trie. This was the perfect opportunity to give my contribution to Effect.

Let's dive in the full process 🚀

Get started

Always start from research:

• What is the best data structure to model a Trie?
• What are some possible challenges?
• How can this be implemented in javascript?

Always make sure to define all the requirements and have a plan for the final implementation

I did the following:

• Search all the details of what a Trie is and how it works
• Learn about different implementations and their tradeoffs
• Collect resources (articles, videos, pseudo codes, algorithms)

At the end I decided to implement a Ternary Search Trie. This structure allows for better space efficiency which is important when working with javascript.

All ready, time to code! 👇

Implementation

The first step is forking the repository and creating a new branch.

The Effect README provides a clear set of guidelines to contribute to the project. Similar guidelines can be found in most open source projects.

Fork > New Branch > Implementation > PR: these are the steps you will follow for any contribution to an open source project

I had no problem while configuring the project locally. Time to dive into code then.

The Art of Reading code

When contributing to an existing project you always need to make sure to follow the existing code conventions.

Step 2: spent some time reading and understanding how the code is structured and what are the code conventions

This process can be slow and frustrating at first. It's about understanding someone else code after all 💁🏼‍♂️

Nonetheless, this is crucial: it's a rite of passage required to become a contributor 🎭

Start by copying

I used the RedBlackTree module already present in Effect as a reference.

If a module has a similar structure, copying and then modifying existing code is perfectly fine

I started by copy-paste the structure of RedBlackTree. I then adapted it to work as a Trie.

This process provided all the foundation to start working on the internals of a Trie data structure.

The Struggle: algorithm complexity

This was not easy indeed 💁🏼‍♂️

Even if the algorithm looks "easy" on paper, the actual implementation has been a struggle:

• Immutability: how can I make a data structure immutable but also efficient?
• Stack safe: in a large data structure recursion can break the stack, therefore no recursion. But how?
• Efficiency: it cannot "just work", it must also be fast

It took me 9 hours to implement the first passing test 🤝

Sending PR and review

Once I had something working I submitted the PR to get feedback:

• Provide a clear and complete description
• Be ready to change the implementation based on feedback and suggestions
• Make sure to follow all the steps provided in the guidelines

PR for a new Trie data structure in Effect

I then iterated over the implementations, fixed some issues, and added more methods and documentation.

I wrote a step by step guide of everything that I learn implementing a data structure in Typescript.

This guide covers everything that you need to know about data structures in Typescript (even some not-so-obvious concepts 🤔)

Takeaways

• Open source is for everyone, in every project. You just need to dive in
• Data structures hide all the complexity in their internal implementation
• Reading code is as important as writing it sometimes: make sure to practice this skill
• No task is too complex: even if the process is not easy, the reward is definitely worth it
• A Trie looks so satisfying 👇

This is how the internal implementation of a Ternary Search Tree looks like. Awesome!

---

This was an amazing experience. I learned so much in the process, not just about Tries but generally about open source, javascript, data structures, and more.

Definitely consider contributing to open source. It's a transformative experience 🔥

See you next 👋