Data Structures and Algorithms with Elixir

Advent of Code was keeping me busy. Also, I am refactoring this which is keeping me busier. However, when I was solving an Advent of Code problem few minutes ago, which made me (lazily) use libgraph and its Graph.strong_components, I realized, I should be implementing that by hand when I have the time. Kosaraju’s algorithm comes to mind.

I also started reading Purely Functional Data Structures and I think it’s pretty well written and (thus far) accessible for all levels.

Some algorithms are pretty hard to think of from a functional point of view. For example, bubble sort is easiest sorting algorithm to implement but took me awhile to think of it without a swap and a for-loop. Same goes for Circular and Bidirectional Linked List. While I implemented them through Zippers (one of the best ways to think of things), it’s not your traditional “linked list” but more like a navigable list.

Going to start a new blog site from next year - dedicated to Elixir (not just algorithms but everything, I took huge inspiration from https://fsharpforfunandprofit.com/ and I want to do something similar (and if I’m having a good day, with 0.001% of the quality) for Elixir.

3 Likes

In your blog posts, you can show different approaches and then the proper functional way. That will make it the best resource for DS&A in Elixir.

4 Likes

Yes, that’s the plan. Also, would make good use of Benchmarking and Property Based Testing while at it.

3 Likes

The good thing is that if you write your blog posts the way you planned, you can later combine those blog posts and that will become a great book. :slight_smile:

4 Likes

Got these two to accompany me throughout 2022 during this. Going to post my first one on Sunday.

6 Likes

Nice! I will be looking forward to reading what you think of them! :003:

3 Likes

td;dr I’m back and expect lots of algorithm + elixir posts here :slight_smile:

So I was burned out and depressed since December. Which is why last year’s AoC thread saw me suddenly vanish, I was less chatty and i had almost 0 personal project contribution this year, until today :smiley:

Been feeling better since mid-feb and am fully motivated and energetic since last week. I started with a lighter data structure like Min/Max Stack and algorithm like Catalan number.

Planning on dealing with Disjoint Set, Lavenstein and starting off with Graph from next week. Stay tuned.

4 Likes

Yes, there should be a book on this using Elixir :slight_smile:

4 Likes

Update March 7, 2022

So yesterday I implemented Catalan Number. It was quite fun. The recursive version choked after awhile but the dynamic programming version crunched away with a decent O(nn) complexity.

There’s more improved algorithm for this which I will visit in the future.

Today, I take on Union Find algorithm. Disjoint sets are fun and they can be prerequisite to future works like cycle detection or minimum spanning tree so looking forward to this. Also, I will probably try linking this library to my Advent of Code one (already ported some algorithms from that repository into here like the Chinese Remainder).

2 Likes

I wondered where you got to! Hope you’re feeling better now :hugs:

We defo need to get some book clubs back on the go! (Currently in the middle of Prag Dave’s Elixir course, but Im definitely up for more once I’ve finished it)

3 Likes

Implemented Union/Find. Going to move over to Graph Algorithms from this week onwards.

DisjointSet

This is so much fun. Missed these things.

@AstonJ looks like the idea of writing a book on the topic isn’t as out of the world as I thought. Maybe in 2023, depending on how it goes.

3 Likes

Awesome - I shall look forward to it :003:

3 Likes

Understood Lavenshtein Distance, going to implement it now. My gut feeling is that with pattern matching, this algorithm will be a breeze to reason with through Elixir.

3 Likes

Hi @mafinar :wave: hope you’re ok, asking your advice with the repo: as a complete beginner, where should i begin with? im seeing:

ex_algo/
├── list/
├── number/
├── queue/
├── set/
├── sort/
├── stack/
└── tree/

massive thanks! :pray: :pray: :pray:

3 Likes

Hello @jaeyson thanks for asking, I’m doing great. Hope you are too.

tl;dr All are stand-alone so you can just click on any link from README and start, but I’ll start with sort and search the terms on Wikipedia and mentally map the pseudocode/data-flow with the Elixir code (following test cases to double check my understanding).

And beyond that tl;dr…

Interesting questions. So far, every algorithm is stand-alone (i.e. no module aliases another, yet.)

So normally, when I was introduced with data structures and algorithms for the first time, I started with searching and sorting, Stack, then Queue and then LinkedList before all hell breaking lose. And when LinkedList, I meant linear linked list not double, circular, xor etc.

So I’d suggest maybe start with sort/ then stack/ and then list/? queue is interesting because of the way it deals with FIFO with zipper.

So normally, a data structure implemented here should first be looked at their respective .ex file, there are doctests to follow, but you can also click on the README links for tests. Some of the tests have Property Tests to give you a “meta” understanding of that data structure. For example, “if I have list of integer and I push them all into a stack and then pop them all out to another list, then they will be inverse of each other” is a statement that is true to any stack. Those tests also give some idea.

I DO have plans to add external links to these data structures so that once you’re looking into say, Catalan Numbers (inside number/) then you can go through all the links that explain it, and also an independent README inside all folders for a detailed discussion of it. But I kept that for future since I want to cover some algorithms first.

Please let me know if this helped, and feel free to suggest more properties or clarification and bugs when you encounter :slight_smile:

4 Likes

super helpful and greatly appreciated :pray: :pray: :pray:, i’ll follow your advice!

3 Likes

Today it was Binary Search. Unfortunately I used Elixir lists for binary search for today’s version, therefore making this an O(n) attempt, equal or worse than linear search. I will try out an array version later, even that’s not O(1) (Nothing is in immutable world?). This is just for showing the mechanism of binary search without any of its benefits gained in a language with real arrays.

Here’s the link: Binary Search

4 Likes

Going to do a deep dive on the internals of Vector as implemented here: GitHub - sabiwara/aja: Extension of the Elixir standard library focused on data stuctures, data manipulation and performance this offers so much learning opportunities for me :smiley:

3 Likes

I’ve read this “Discrete and combinatorial mathematics” at the beginning of this year, hard reading, very hard)

3 Likes

I don’t feel the challenge perhaps because i took two courses where i consulted this book (at one it was the main textbook) in the university and the instructor was amazing.

I love that book and that topic. Brings back a lot of fond memories.

2 Likes