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

241–250 of 259 posts

Re: The hunt for the missing data type

#241

Post by eru »

Datalog is great, but you don't need it. You can have relations as datastructures in more conventional languages and still reap many benefits.

I programmed professionally in a system that was a dialect of Haskell that had relations as a standard library data type. Expressing business logic in them was very pleasant.

I've also toyed around with adding relations to Python; that also worked just fine. (My toy library wasn't very fast: all operations were implemented naively. But it was still expressive.)

Re: The hunt for the missing data type

#242

Post by eru »

dataflow wrote: post #236
maxiepoo wrote: post #217

Earlier quoted context omitted.

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.

I think we might be speaking past each other? How is enum in Rust a tree type? You might be able to use it to create a tree type, but that's no different from using struct to make struct Tree : std::vector {}; in C++. That wouldn't mean C++ has a tree type, it just means it's not hard to create your own. Whereas std::list is actually a linked list type that's already there.

Well, std::list is something you can create with C++ code (and likely is in most implementations of C++?), it doesn't need any special support. So I can see why someone might not treat std::list as any more special than a tree datastructure supplied by a different library?

However, algebraic data types really make your life easier, and more languages should have them.

Re: The hunt for the missing data type

#243

Post by eru »

nyrikki wrote: post #162
skybrian wrote: post #154

Earlier quoted context omitted.

For importing and exporting data, it often makes more sense to use something like a table or a tree rather than a graph. (Like a CSV file or a JSON file.) So it's not clear what the interface would do. What methods should there be? Again, there are too many choices, and a Graph interface often isn't the best way to represent a view of some subset of a graph.

To add to this, recursively enumerable is the same as semi-decidable, and that only gets you to finite time. One of the big reasons to fight to make dependencies DAG like is because exhaustive search gets you to exponential time. NP-complete, NP-hard are easy to run into with graphs. Graph k-colorability, finding Hamiltonian cycles, max cliques, max independent sets, and vertex cover on (n)vertex graphs aren't just N…

Btw, solving practical instance of NP problems is often not all that bad in practice. Even solving them to optimality.

But you need to move away from writing your own solvers. Instead you use a library that lets you describe your problem, and then throws off-the-shelf solvers at them. See eg https://developers.google.com/optimization

That's a good approach even for problems that are in P, because minor changes in the business logic requirements often only translate into minor changes in the programmatic problem description, but would translate to major changes in the a bespoke, custom algorithm to solve them, even if everything stays in P.

It also separates the description of the problem from the solution. In the real world, the business logic requirements are seldom written down explicitly somewhere, and are only available implicitly as described by the code. So without this separation, it can be hard to disentangle what's a real requirement, and what's just something your custom heuristic algorithm happens to spit out.

Re: The hunt for the missing data type

#244

Post by eru »

sanderjd wrote: post #104
nickpsecurity wrote: post #43

Earlier quoted context omitted.

You might say graphs are an abstract concept, solving our problems requires specialized graphs, and so we just use or build the kind we need.

Yeah this is exactly how I think of it. I think "graphs" are just at a different level of the abstraction hierarchy than the data structures they're often grouped together with. This is even further up the abstraction hierarchy, but to illustrate the point, nobody really wonders why languages don't ship with a built-in database implementation. And it's the same basic reason as with graphs; one size doesn't fit most.

Well, the original article actually describes that relations are great way to model graphs, and suggests that your language (or its standard library) should ship with a good datastructure for relations.

You would get most of a what you need for a simple relation database this way.

Re: The hunt for the missing data type

#245

Post by eru »

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…

> You can't really do that with a graph.

Why not? Relations model graphs really well, and you could have a relation datastructure in your language (or its standard library).

Re: The hunt for the missing data type

#246

Post by eru »

somat wrote: post #84
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.

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.

You can use a pointer when building a graph data structure. You can also use numeric indices into arrays. Or you can store your graph in an entirely different way.

You are right that the data representation itself is only one small part of a data structure, the operations on that representation are also really important.

Re: The hunt for the missing data type

#247

Post by eru »

atoav wrote: post #188
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.

Puthon has one, as mentioned, but as a non CS-person I never encountered any problem in my programming-life that so fundamentally called for graphs that I needed one, not did I had so much fascination for graphs that it was a tool I wanted to force onto my problems. I guess it is just that there are many problems that can be solved incredibly well without graphs and not that many where graphs outshine everything else…

Two people can look at the same solution to the same problem, and interpret and analyse it differently.

Some of those interpretations can involve graphs, but that's not necessarily intrinsic to the problem nor solution.

Re: The hunt for the missing data type

#248

Post by kolinko »

atoav wrote: post #188
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.

Puthon has one, as mentioned, but as a non CS-person I never encountered any problem in my programming-life that so fundamentally called for graphs that I needed one, not did I had so much fascination for graphs that it was a tool I wanted to force onto my problems. I guess it is just that there are many problems that can be solved incredibly well without graphs and not that many where graphs outshine everything else…

What kinds of projects did you build? I'd risk saying that it's more likely you just didn't spot where graphs could be useful, or you implemented a graph not recognising it as such.

Even if you work with pure webdev - the least CS-requiring field of all programming, if you work with DOM, it's a tree/graph structure, or if you work with a sitemap - it's a graph.

From my experience working with non-cs programmers, they tend to struggle with finding solutions to problems that would be solved instantly with graph structures. Or they write suboptimal code because they end up doing BFS, where they should DFS, or brute force when they could use a specific graph algorithm.

Re: The hunt for the missing data type

#249

Post by kthielen »

gue5t wrote: post #28

One interesting perspective is to view the sequence of lists -> trees -> DAGs -> general graphs as a loosening of restrictions: - list nodes may have one child - tree nodes may have multiple - DAG nodes may have multiple parents though restricted by topological ordering - graph nodes may have multiple parents from anywhere in the collection Lists and trees can be fully captured by sum and product types, but extending…

> Lists and trees can be fully captured by sum and product types, but extending this representation style to DAGs and graphs doesn't work--you either get inefficiency (for DAGs) and then infinite regress (for cyclic graphs) attempting to continue the "syntactic" style of representation

You also need "inductive" recursive types to represent lists and trees, in addition to sums and products.

One way of representing the type of a list of T is like:

mu X.1+T*X

(Hence sum and product types, but also inductive or "least fixed point" recursion.)

But you can also use "coinductive" recursive types to represent "processes" (or "greatest fixed point" recursion) with almost the same notation:

nu X.1+T*X

This represents a FSM which at any point yields either a termination (the "1" on the left side of the recursive sum) or a value and a continuation (the "T" in "T*X" is the value and the "X" in "T*X" is the continuation).

This doesn't answer every question about graph representation, obviously, but it's a useful tool for attacking some graph problems you'd like to represent "syntactically" as you say (though you have to think in terms of "coinduction" instead of "induction" e.g. bisimilarity instead of equality).

Re: The hunt for the missing data type

#250

Post by nyrikki »

eru wrote: post #243
nyrikki wrote: post #162

Earlier quoted context omitted.

To add to this, recursively enumerable is the same as semi-decidable, and that only gets you to finite time. One of the big reasons to fight to make dependencies DAG like is because exhaustive search gets you to exponential time. NP-complete, NP-hard are easy to run into with graphs. Graph k-colorability, finding Hamiltonian cycles, max cliques, max independent sets, and vertex cover on (n)vertex graphs aren't just N…

Btw, solving practical instance of NP problems is often not all that bad in practice. Even solving them to optimality. But you need to move away from writing your own solvers. Instead you use a library that lets you describe your problem, and then throws off-the-shelf solvers at them. See eg https://developers.google.com/optimization That's a good approach even for problems that are in P, because minor changes in the…

Many graph problems also end up having lower bounds, being subject to conjectures like SETH or 3sum

SETH has a sub quadratic lower bound and several other graph problems have cubic lower bounds.

Many real systems are often saved because it is actually hard to write code that aren't primitive recursive functions.

Cycles often are what destroy that, as considering WHILE and GOTO being the difference between primitive and general recursive functions helps show.

If you consider NP as second-order queries where the second-order quantifiers are only existantials, That will help explain why heuristics (educated guesses) help.

A graph data type wouldn't have those heuristics.

Post reply on HN