Exads - Elixir Algorithms and Abstract Data Structures Collection

Your Libraries & OS Mentoring Libraries
1

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.

Here’s the repo: Exads

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 :slight_smile:

9 Likes
2

Good luck with this Sasha - sounds like an interesting project :slight_smile:

1 Like
3

Really awesome, and really useful! Starred for future reference :smile:

2 Likes
4

Thank you @ramonsnir :slight_smile: Please feel free to contribute in any way if you want. We’re two people working on it so far.

1 Like
5

I opened a pull request to add Travis CI and Inch CI badges :slight_smile: Cheers!

2 Likes
6

@uranther Thank you! Already merged and resolved the conflicts for both Travis CI and Credo. The build is passing :slightly_smiling:

Next I’ll be looking to implement the Inspect behaviour and maybe review the Priority Queue based on some things @NobbZ and me talked about.

One thing I thought of is to look at Enum.sort and see if we can implement a better algorithm (if possible).

2 Likes
7

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.

For example, compare the imperative pseudo-code of insertion sort with its implementation in Haskell. The latter is so much easier to understand because it captures the high-level concepts.

Check out Purely Functional Data Structures by Chris Okasaki. This book may be more helpful for this project, although it doesn’t have all the ADS you list in the README. There’s also Pearls of Functional Algorithm Design.

Elixir just uses :lists.sort, which is an implementation of merge sort (source).

8

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 :slight_smile: 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.

1 Like
9

According to the internets:

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?

Another option is to parallelize the merge sort. :astonished:

1 Like
10

I’ll assign this task for myself, if you don’t mind (research about better sorting algos and write a parallel merge sort) :slightly_smiling:

1 Like
11

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.

6 Likes
12

It seems the project has been put on the back burner for everyone. Would love to see it resurrected.

13

For now you could use @Qqwy’s libraries. :slight_smile:

1 Like