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