# Data Structures and Algorithms with Elixir

This is going to be a long an frequently posted thread.

While talking to a friend of mine who has taken data structure and algorithm course, I realized, whenever I “think” about algorithms, Java is the first thing that comes to mind. While I did solve a lot of programming puzzles in functional programming languages, I don’t remember ever taking myself through the shoes of course takers of those courses in a functional (or even dynamic) languages.

So this is what I am doing, I am going to read about an algorithm or two per week, and then try to see it through Elixir. And share the code, and leave myself notes for here, unless I can organize those thoughts well enough to put up in my blog.

I already started this few days ago and made okay progress. Here’s the repository.

I have a few naively implemented algorithms out there, will regularly revise them or update new ones.

Not using any book as reference yet, but when I will I would draw inspiration from the following books:

And when I find the courage:

I do not intend this to be used by anyone seriously as this will never be “production-ready”, this repository is to keep myself educated about algorithms and thinking through zippers and lenses.

10 Likes

I look forward to following your progress Mafinar!

Sounds like a good title for a book too - who knows, maybe you’ll end up writing it one day!?

1 Like

2 Likes

Sure after a few years!

2 Likes

Dealt with `CircularList` yesterday, and while playing around with it in the REPL, realized an important issue I overlooked in the `LinkedList` implementation.

The most joyful part of the work so far was the property testing bit. Things like, “if I keep checking the `nth` element of a `CircularList` that goes beyond the length, the n-th element will really be n module length.” is something where I can just use `StreamData` and not waste my brain cycles coming up with examples.

Not using `PropEr` but `StreamData` as I found the latter to be friendlier to my Elixir mind (OMG I almost typed `Pythonic` here! The past year I’ve been doing Python and I think that is taking over my muscle memory now!)

2 Likes

Today I intend to do a `BidirectionalList` – Zipper if you will! I think Zipper is one of the best things happening to functional programmers. Every time I read Huet’s paper, I feel that aha moment I felt the first time, such a clever way to look into data structures!

3 Likes

I won’t lie, reading up all these blog posts and papers makes me want to understand Haskell.

3 Likes

@mafinar write a book on Data Structure and Algorithms in Erlang/Elixir and we’ll be your first readers.

4 Likes

I just started reading Purely Function Data Structure. Such a good book, I had FUD around it for nothing. While not sure about my having to do anything wuth it- I agree we need an Elixir + Algorithm book.

3 Likes

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.

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!

3 Likes

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

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

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

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

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