Hi everyone, some time ago I started building an algorithm and data structures collection for Elixir. My goal is to build the best and most complete collection of algos and ADS’s for Elixir, to be available for everyone to use as they need. So far I’ve started implementing the most popular data structures, like the Stack, Queue and Binary Search Tree. However, in order to have a really good collection that’s robust and complete, I will surely need some contributions.
I’m taking contributions in every form, be it corrections, new implementations, new algorithms or data structures or even test suites for the existing ones. Everyone’s free to contribute and I’ll accept most contributions as long as they reach a decent standard of quality (decent code, justifications for changes, and so on). But hey, even if you’re not sure if it’s good, please send them to me and maybe we’ll work together on it to make it better and merge it into the project. There’s a lot of people learning Elixir in this community and I think this would be a great way to learn and get some experience with the language.
In the README you have a roadmap of the algos and ADS’s I have on my mind right now, but I plan to implement more than those, so feel free to work on whatever you like, even if it’s not in the roadmap right now.
I’ve been writing some stories on Medium about this project. I just posted the second chapter about implementing the Binary Search Tree: Implementing the BST
As I’ve said, everyone’s free to help and also to critique my work (and writing skills) as long as it is constructive and helpful
I noticed you mentioned you are basing your algorithms & data structures on those in Introduction to Algorithms. I took a peek, and about lost it at the stateful, imperative implementations of the algorithms. I guess that is to be expected, but it makes it difficult to translate to a functional language.
Yes, I’ve been refering to it because it’s the “standard book” for Algos and ADS (at least it is in most universities I’ve checked, including mine). I didn’t know about that Purely Functional Data Structures book, I’m going to check it out Thanks!
I still hadn’t checked Elixir’s implementation. In that case, shouldn’t Quicksort be better in terms of space, because of in place sorting? Not sure if this only applies to the imperative languages.
Merge sort is often the best choice for sorting a linked list: in this situation it is relatively easy to implement a merge sort in such a way that it requires only Θ(1) extra space, and the slow random-access performance of a linked list makes some other algorithms (such as quicksort) perform poorly, and others (such as heapsort) completely impossible.
Seems to make sense. Maybe there are more advanced sorting algorithms that are well-suited for linked lists?
I will second this book. It goes into details about performance in FP style that most of us (or me at least) didn’t get in Algorithms class. Those classes seem to focus on imperative style analysis. This book introduces amortization and banker’s method. You can check out the full text here.