The hunt for the missing data type • Hacker News Board

Re: The hunt for the missing data type

#211

Post by gpderetta » Tue, Mar 05, 2024, 11:48 AM UTC

throwaway2037 wrote: post #182

The C++ Standard Template Library is now 29 years old. It doesn't have a graph (or generic B-tree) data structure. That says it all for me. In my too many years of programming, I have only needed to program a graph structure once or twice. Yes, the are "ubiquitous in software engineering", but still incredibly rare in most enterprise programming projects.

Boost does have the BGL (which, following the STL, abstracts graph algorithms from graph implementations). But I don't think it has seen significant updates in more than two decades.

Re: The hunt for the missing data type

#212

Post by swiftcoder » Tue, Mar 05, 2024, 12:00 PM UTC

paulddraper wrote: post #98

obi1kenobi wrote: post #3

As someone who did a lot of work with graphs, "why don't programming languages have a built-in graph data type?" is a question I’ve been asked a million times. I'm thrilled I'll be able to point folks to a much more in-depth analysis like the one here, instead of saying some variation of "it's really hard to do it well" and having them just take my word for it.

> "it's really hard to do it well" More importantly, there are a lot of tradeoffs. Virtually every language offers a hash map. You can roll your own to outperform in an individual circumstance, the default works pretty well. You can't really do that with a graph. Maybe if you offered a bunch of graph types. --- PS. Bit of trivia: Java's HashMap is a bit different from almost every other language in that it lets you t…

It's also a bit different in that every insertion entails at least one allocation, and every lookup entails pointer-chasing through at least 3 dereferences. Java's lack of proper value types really kneecaps their hashmap implementation in many practical performance scenarios...

Re: The hunt for the missing data type

#213

Post by swiftcoder » Tue, Mar 05, 2024, 12:02 PM UTC

js8 wrote: post #151

rhelz wrote: post #79

Ya, the central obstacle is that: 1. for simple and small graph problems, a simple vector-of-vectors adjacency list is easy enough to code up. 2. For complex and huge graph problems, the only way to get performant solutions is to tailor the graph implementation to the specific details of the problem to be solved. And its hard to see what kind of language support would help, other than just having a super-smart compil…

> we are really good at code sharing of small things like vectors, and of large things like operating systems. Its the middle-sized problems we are bad at. Interesting. But I am not sure we are good at sharing small things - every programming language has its own implementation of vectors. Within one language ecosystem, the API of a vector is small, and that's probably what makes it easy to share. For operating syste…

> every programming language has its own implementation of vectors

Many programming languages have more than one implementations of vectors. Turns out you want tiny vectors stored on the stack, and big vectors stored on the heap...

Re: The hunt for the missing data type

#214

Post by rdtsc » Tue, Mar 05, 2024, 12:46 PM UTC

ogogmad wrote: post #201

rdtsc wrote: post #108

> There’s a gap between how often software engineers could use graphs and how little our programming ecosystems support them. Where are all the graph types? They've been there for quite a while :-) https://www.erlang.org/doc/man/digraph.html https://www.erlang.org/doc/man/digraph_utils And if you want to do some set theoretical stuff you're covered as well: https://www.erlang.org/doc/man/sofs.html

How flexible and performant is that in different situations?

I had never used it, aside from a simple dependency checker. But I know the compiler and the Erlang types analyzer (dialyzer) uses them.

Re: The hunt for the missing data type

#215

Post by BlindEyeHalo » Tue, Mar 05, 2024, 1:32 PM UTC

jkaptur wrote: post #111

I've often wondered about a missing application: "Excel for graphs". Just like Excel for tabular data, it would support RAM-sized data (enough to require a computer, but not so much that you need a data center), implement lots of algorithms and visualizations "well enough", and require no programming skill to operate. As the article says, a lot of our real-world problems are graph problems - why are programmers the o…

> As the article says, a lot of our real-world problems are graph problems - why are programmers the only ones who should have the tools to solve them?

I think programmers and mathematicians are the only ones that model these problems as graphs. I doubt a casual person sees graphs in random real world problems.

And something I learned working in a big corporations, everything can be an excel spreadsheet if you try hard enough.

Re: The hunt for the missing data type

#216

Post by jcgrillo » Tue, Mar 05, 2024, 2:07 PM UTC

jerf wrote: post #16

This is a good article and I endorse it. I would supplement it with the observation that when I was a younger programmer, like many people, I considered "generic" or "flexible" a positive when describing a library or framework. I have come to see it as generally negative, especially when the developer's summary puts these adjectives or something similar front and center. Let me show you the most flexible possible Jav…

> Even if you nail down the problem to exactly one representation, they still don't fit.

This is exactly the problem I've found with graph databases. I've never successfully used a graph database to solve a problem, and multiple other engineers I've spoken to have bounced off them in a similar way. The problem is I don't have an arbitrary graph problem, mine is specific, and as you say the choices a graph database makes matter. It really gives me greater appreciation for the relational model because so many things can be made to work on a relational database. It may not be elegant, but it works.

I think the way I'd like to approach graphs, if I do it again, would be to use a graph represented as sparse matrices in memory as an index. This is more or less in line with what you get from expressing the graph problem in application code, but maybe easier to understand and maintain? I guess that is to say I'm still optimistic there might be some general purpose solution like RedisGraph (now FalkorDB) that makes sense to use this way, but I'm not sure I'd try to use an out-of-core graph database again.

Re: The hunt for the missing data type

#217

Post by maxiepoo » Tue, Mar 05, 2024, 2:34 PM UTC

dataflow wrote: post #174

obi1kenobi wrote: post #3

As someone who did a lot of work with graphs, "why don't programming languages have a built-in graph data type?" is a question I’ve been asked a million times. I'm thrilled I'll be able to point folks to a much more in-depth analysis like the one here, instead of saying some variation of "it's really hard to do it well" and having them just take my word for it.

> "why don't programming languages have a built-in graph data type?" What I find a little funny about that question is that people miss the fact that there isn't even a tree data structure in most languages. Most languages have static arrays, dynamic arrays, linked lists, and... that's it as far as structural types go. Everything else (BSTs, hashtables, etc.) is some semantic abstraction that hides some capabilities…

Typed functional languages like Haskell (data)/ML (type) do have a built-in way to define new tree types, and so does Rust (enum). It's one of the biggest things I miss when I'm not using these languages, especially when combined with some metaprogramming (deriving/derive) to get some functions defined for these new types very quickly.

Re: The hunt for the missing data type

#218

Post by maxiepoo » Tue, Mar 05, 2024, 2:35 PM UTC

rb-2 wrote: post #9

I wonder if it would be possible to mathematically define (in a theorem proving language like Coq) a bunch of accessor methods as well as a bunch of implementation primitives and then "compile" a custom graph implementation with whatever properties you need for your application. Some accessor methods will be very efficient for some implementations and very inefficient for others, but every method will still be availa…

You can do something like this with OCaml/SML's module system.

And certainly from an abstraction point of view you can do this in any dependently typed language like Idris/Agda/Coq, but these don't have great implementations.

Re: The hunt for the missing data type

#219

Post by platz » Tue, Mar 05, 2024, 3:11 PM UTC

superlopuh wrote: post #207

This is basically my PhD thesis proposal, I don't think there's any fundamental technological problem here, just that for a graph to be efficient to process you need high-level optimisations that can take mathematical properties of graphs into account. For that you need to either reimplement a compiler into your framework, or be integrated into an existing compiler, both obviously take a lot of work. Some comments he…

How will I have any expectations of run-time behavior if I have to hope that my graph will fuse or fail to fuse at run time?

Reminds me of the issues that haskell programmers face when an innocuous change causes list fusion to fail tanking performance; to know how to coax the compiler to fuse again you have to have intimate knowledge of how that fusion process works which isn't visible in the API; you need knowledge of compiler implementation/behavior.

programmers do not like this kind of instability.

Re: The hunt for the missing data type

#220

Post by dataflow » Tue, Mar 05, 2024, 3:27 PM UTC

saghm wrote: post #193

dataflow wrote: post #173

Earlier quoted context omitted.

> Fundamentally, all I need to define a graph is a set of vertices v \in V and function Neighbors(v). Even that is severely overconstrained. It doesn't allow multiple edges to the same neighbor!

Maybe the naming would be a little weird for that use case, but they didn't specify what the output of `Neighbors(v)` is; I don't see any reason why it couldn't return a multiset or a relation (w, c) where `c` is the number of connections between `v` and `w`

Returning the same neighbor multiple times kind of misses the point. The point was that you need to return edges (not neighbors) because the edges connecting the same neighbors can be different.

Like, imagine two train lines between the same pair of stations. Or two roads between the same intersections. They might have different travel times, costs, etc.