Data Structures and Algorithms with Elixir

AstonJ · 2021-11-26T23:24:54.093Z

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!?

mafinar · 2021-11-26T23:34:30.869Z

Sure after a few years!

mafinar · 2021-11-27T14:11:37.344Z

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!)

mafinar · 2021-11-27T14:14:35.382Z

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!

mafinar · 2021-11-27T14:15:43.628Z

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

DevotionGeo · 2021-11-28T14:19:24.919Z

AstonJ:

Sounds like a good title for a book too

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

mafinar · 2021-11-28T16:26:52.825Z

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.

mafinar · 2021-12-19T07:25:25.339Z

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.

DevotionGeo · 2021-12-19T08:28:58.870Z

mafinar:

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.

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.

mafinar · 2021-12-19T08:32:53.557Z

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

DevotionGeo · 2021-12-19T08:34:07.753Z

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.

mafinar · 2021-12-24T00:40:15.783Z

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

20211223_1656401200×880 58.1 KB

AstonJ · 2021-12-24T00:47:08.815Z

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

mafinar · 2022-03-07T03:20:44.675Z

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.

andrea · 2022-03-07T06:42:12.875Z

Yes, there should be a book on this using Elixir

mafinar · 2022-03-07T15:17:23.697Z

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).

AstonJ · 2022-03-07T16:18:25.726Z

mafinar:

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

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)

mafinar · 2022-03-08T00:57:39.006Z

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.

AstonJ · 2022-03-08T16:57:36.005Z

Awesome - I shall look forward to it

mafinar · 2022-03-10T04:21:32.232Z

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.