Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The hunt for the missing data type

hillelwayne.com

Post reply on HN
Print view View original

141–150 of 259 posts

Re: The hunt for the missing data type

#141

Post by andyferris »

alanbernstein wrote: post #88
somat wrote: post #84

Earlier quoted context omitted.

This is a super naive take. but I would consider the pointer the be the native graph type. What is wanted is not a graph type but the tooling to traverse graphs.

Maybe a pointer is better described as equivalent to a half-edge?

I think this might be kinda right.

Take rust. Tree edges use Box, and DAG edges use Arc or Rc. Rust doesn’t really help with building non-DAG graphs as native data types - you can drop back to using “handles” for more generic graphs.

And I actually think that is kinda fair. Languages and standard libraries should support trees and DAGs out of the box. Perhaps Hillel is right that more complex graphs should be in a user-space library or something.

Re: The hunt for the missing data type

#142

Post by gloftus »

ylow wrote: post #123

I think this is because a graph is not a data-structure nor a data-type. It is really an abstraction. Fundamentally, all I need to define a graph is a set of vertices v \in V and function Neighbors(v). And that really is all is needed for the most foundational set of graph algorithms. Everything else are case-by-case constraints. Does A->B imply B->A? is the node set partitionable with certain constraints? Are there…

Yes, graphs are ubiquitous because they are so abstract. They live on the same level of abstraction as pure numbers. There are useful "numerical" libraries that exist, and by analogy I think you could say there are also useful "graphical" libraries that exist. But we don't really have "number" libraries, and we don't really have "graph" libraries, because those concepts are a bit too abstract to write APIs against.

Re: The hunt for the missing data type

#143

Post by kjqgqkejbfefn »

swagasaurus-rex wrote: post #129
criloz2 wrote: post #72

Graph drawing tools are also very underwhelming, they work pretty good for small graphs until you have something like 500 nodes or more, then eventually their output becomes complete incompressible or very difficult to look at it, they miss the ability to automatically organize those graph in hierarchical structures and provide a nice interface to explore them, we are used that everything around us have some kind of…

The illustrations I've seen of neural networks really highlights the sheet incomprehensibility of visualizing large graphs

https://www.microsoft.com/en-us/research/wp-content/uploads/...

Re: The hunt for the missing data type

#144

Post by rocqua »

twoodfin wrote: post #121
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…

And its hard to see what kind of language support would help, other than just having a super-smart compiler which could analyze the code and determine whether an adjacency list, matrix, 3d array, etc was the best way to implement it. That's the kind of optimization which we won't see in compilers for a while. I’m not so sure? Looking at an algorithm against an abstract graph type, then filling in the implementation t…

My experience with cipher is that the query optimizer doesn't know enough about the graph to pick up on trivial optimizations. This can't be fixed without a way to tell the optimizer about those properties, and even just dreiging a language to tell the optimizer those things is difficult.

Just an LLM looking at your query isn't going to cut it. It will need to take your actual data into account.

Re: The hunt for the missing data type

#145

Post by e_y_ »

skrebbel wrote: post #96

I think most languages support representing many kinds of graphs very well, particularly directed graphs without data on the edges: with objects, lists, and object references (or pointers). A tree is a graph. A typical Java-style object composing other objects composing other objects again, etc etc, often with cycles and parent backreferences and whatnot, is a graph. The html DOM is a graph. I recognize that these ar…

Back in the C days, it was common to not use generic data structures like lists; instead you'd have a next_item pointer as a field in the struct. For linked lists, this would save you from needing another memory allocation or wrapper struct, and since C doesn't have templates you'd either have to blindly cast the type or use macros or write a type-specific iterator anyways.

Lists eventually became a standard language feature in C++ and other languages, but it's trickier for trees and graphs. Taking the DOM example, you might be searching through child elements (div, span, etc) or nodes (text nodes, comment nodes) and different operations might only work with a specific subset of the "edges". There might be pointers to other objects, like from a DOM node to accessibility tree node. You might even have multiple parent node pointers, such as a pointer that takes you to the nearest shadow root or something.

Since there are multiple ways to traverse the same data structure, generic functions don't work on it. You could create a separate tree/graph for each thing you want to use it for, but that takes additional memory and has to be updated when the original struct changes. Or you could create some kind of adapter that has a get_edges() function, but this might not be very well optimized or might be clunky for many other reasons. So it usually just ends up being simpler rolling your own functions instead of using a library.

Re: The hunt for the missing data type

#147

Post by lmm »

hobofan wrote: post #47

I think the post mostly answers the questions "why are graph _algorithms_ not better supported in programming languages", with a focus that is much more on "big data" graph processing than graph support in general. I think if you look at graph support in general you are also looking at wider questions, like "why are OGMs (Object Graph Mappers) not as popular as ORMs" and "why is JSON so prevalent while RDF (or anothe…

> Joins are first-class entities in SQL. They even have their own keyword (hint: it starts with J and ends with OIN) ;)

Having its own keyword is pretty strong evidence that something isn't first-class (e.g. typeclasses are not first-class in Haskell; control flow is not first-class in most programming languages).

Re: The hunt for the missing data type

#148

Post by actionfromafar »

e_y_ wrote: post #145
skrebbel wrote: post #96

I think most languages support representing many kinds of graphs very well, particularly directed graphs without data on the edges: with objects, lists, and object references (or pointers). A tree is a graph. A typical Java-style object composing other objects composing other objects again, etc etc, often with cycles and parent backreferences and whatnot, is a graph. The html DOM is a graph. I recognize that these ar…

Back in the C days, it was common to not use generic data structures like lists; instead you'd have a next_item pointer as a field in the struct. For linked lists, this would save you from needing another memory allocation or wrapper struct, and since C doesn't have templates you'd either have to blindly cast the type or use macros or write a type-specific iterator anyways. Lists eventually became a standard language…

Bonus points for not allocating space for the next pointer if you didn’t plan to use it…

Re: The hunt for the missing data type

#149

Post by js8 »

Another data type that would be quite useful is a table (like in a database). For the same reasons, too many design choices.

Anyway, that being said, I have felt that progress will be made in programming languages if the compiler gets to choose an implementation of a data structure, kinda like when a database chooses an execution plan. So you just use an abstract structure (like sequence, map, set, table, graph) and based on the program profile, the compiler will pick the specific implementation. It will also transform the structure into another isomorphic one as needed. (Some programming languages already do something like this, for example, array of structs to struct of arrays conversion.)

Post reply on HN