Recursive graph

Recursive graph or not? Or, infinite data structure or not?

While working on implementing a graph database in my spare time, I had troubles choosing the right data structure for the graph. That’s the cornerstone of the whole thing, so some serious thinking was needed to get this base design decision right, because the rest of the implementation is going to depend a lot on it.

The critical part was to choose between a recursive or a non recursive representation. In the presence of cycles, the recursive version is infinite. Below is the conclusion of what I chose, after evaluating the strong points of each approach.


Non recursive:

Verdict: non recursive. I know, disappointing. But here’s why I chose it.

First, it’s simpler to work with. At least for me, i.e. the whole team. I know better the world of finite containers; I can focus more on the choice and tuning of algorithms than on implementing them in the first place.

I want to move on and now I’m kinda stuck, so let’s put a bookmark there and go forward. Anyway, now I’m aware of the trade-offs, which is also an important aspect. It’ll help me reason about the code.

Avoiding recursivity can however be limiting later down the road. Or to put it differently, I don’t know exactly what I am leaving behind me. I have a good feeling, but still. You don’t know what you don’t know. Time will tell.

I can always switch back later on if needed. If this happens, it’s going to be expensive in time, but it’s a home project, and that’ll be a good opportunity to try refactoring large parts of a Haskell code base. What this tells me is that I have to carefully design my interfaces to allow such a change down the road.

What do you think? Would you have made the same decision?