1

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:

  1. A Common-Sense Guide to Data Structures and Algorithms, Second Edition: Level Up Your Core Programming Skills by Jay Wengrow (pragprog.com)
  2. Advanced Algorithms and Data Structures (manning.com)

And when I find the courage:

  1. Purely Functional Data Structures: Okasaki, Chris: 9780521663502: Books - Amazon.ca

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.

13 Likes
2

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

1 Like
4

Sure after a few years!

2 Likes
5

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
6

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
7

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

3 Likes
8

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

4 Likes
9

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
10

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
11

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
12

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

3 Likes
13

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
14

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

20211223_165640
20211223_1656401200×880 58.1 KB

6 Likes
15

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

3 Likes
16

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
17

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

4 Likes
18

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
19

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
20

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.

4 Likes
21

Awesome - I shall look forward to it :003:

3 Likes