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

21–30 of 259 posts

Re: The hunt for the missing data type

#21

Post by abeppu »

jes5199 wrote: post #11

I think this is a cop-out. Someone in the 1990s could have written the same thing about collections, or dictionaries, but we eventually came up with good-enough compromises that Python, Ruby, and Javascript all basically do the same thing. They don't implement literally every case, but they are good enough for "small" data, where the definition of "small" has grown to be quite large by human standards. I think the re…

And some languages (e.g. java, scala) have standard libraries with interfaces that describe ordered collections, dictionaries, etc, but offer multiple implementations so the programmer can pick based on their specific considerations, but still benefit from library code written around the interface.

Re: The hunt for the missing data type

#22

Post by jes5199 »

gilleain wrote: post #19
jes5199 wrote: post #11

I think this is a cop-out. Someone in the 1990s could have written the same thing about collections, or dictionaries, but we eventually came up with good-enough compromises that Python, Ruby, and Javascript all basically do the same thing. They don't implement literally every case, but they are good enough for "small" data, where the definition of "small" has grown to be quite large by human standards. I think the re…

What do you mean by "textual graph literal"?

Textual array literal: [1,2,3]

Textual dict literal: {"a": 1}

Textual graph literal: ???

Re: The hunt for the missing data type

#23

Post by montmorency88 »

I'd highly recommend Erwigs FGL library in Haskell as a really nice example of a generally performant graph data structure that is easy to work with. The API feels like working with lists because you are essentially consing contexts(node, neighbours) into a list of contexts that form your graph. Many standard graph algorithms are then built up from depth or breadth first search and you can compose really succinct programs to manipulate the graph. Graphs are labelled with any Haskell data structure and there is a graphviz library complementary to FGL to generate dot files which can be rendered according to the data carried in the node labels. Often in an application you want to both perform computations on your graph and render a visualization simultaneously to the end user or for debugging and in FGL you minimise duplication of application and rendering logic.

Re: The hunt for the missing data type

#24

Post by mizzlr_ »

graph is a data structure, not a data type. if you squint enough pointers are the building blocks (the data type is you please) for building graph data structure. a->b is pointer access, looks like an edge in the graph.

graph data structure is parent of tree, code execution/ function call stacks work like a tree, think flame graphs.

stacks and pointers are baked in assembly and cpu architecture. your claims can't be farther from the truth.

Re: The hunt for the missing data type

#25

Post by gilleain »

jes5199 wrote: post #22
gilleain wrote: post #19

Earlier quoted context omitted.

What do you mean by "textual graph literal"?

Textual array literal: [1,2,3] Textual dict literal: {"a": 1} Textual graph literal: ???

Heh, one possibility is:

AB 0:1(C),0:2(D)

For a three node graph with edges between vertex 0 and 1, and vertex 0 and 2, vertex labels 'A' and 'B' and edge labels 'C', and 'D'. Not great to parse (as I sadly found), but possible to read.

Re: The hunt for the missing data type

#26

Post by PaulHoule »

jes5199 wrote: post #11

I think this is a cop-out. Someone in the 1990s could have written the same thing about collections, or dictionaries, but we eventually came up with good-enough compromises that Python, Ruby, and Javascript all basically do the same thing. They don't implement literally every case, but they are good enough for "small" data, where the definition of "small" has grown to be quite large by human standards. I think the re…

I've been involved with RDF and sometimes it seems the gap between "too simple to use RDF" and "too hard to use RDF" is tiny.

For instance I tried to pitch a data processing library a bit like

https://www.knime.com/

but where RDF graphs (roughly like a JSON document) get passed over the "lines" but found that the heavy hitters in this space believed this sort of product has to use columnar execution to be "fast enough". You can certainly build something that can do operations on a dynamic RDF graph (really a set of triple) but in principle you could compile code that treats native data structures as if they were in RDF... You might get pretty good in speed but it won't be as fast as native and hard to make it easier to code for than native.

Re: The hunt for the missing data type

#27

Post by Hackbraten »

abeppu wrote: post #21
jes5199 wrote: post #11

I think this is a cop-out. Someone in the 1990s could have written the same thing about collections, or dictionaries, but we eventually came up with good-enough compromises that Python, Ruby, and Javascript all basically do the same thing. They don't implement literally every case, but they are good enough for "small" data, where the definition of "small" has grown to be quite large by human standards. I think the re…

And some languages (e.g. java, scala) have standard libraries with interfaces that describe ordered collections, dictionaries, etc, but offer multiple implementations so the programmer can pick based on their specific considerations, but still benefit from library code written around the interface.

It also uses hint/marker interfaces (eg. `RandomAccess`) so the library code can choose among algorithms internally while still presenting an uniform API to the client.

Re: The hunt for the missing data type

#28

Post by gue5t »

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 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, or you need to adopt an "indirect" representation based on identifiers or indices or hash consing.

Re: The hunt for the missing data type

#29

Post by taeric »

A graph, as presented in this article, is a model of something else. That we have more than one way to implement this model is rather natural, all told. The hope that we can have a singular syntax and data structure that represents a graph in code is almost exactly why the author of Java's Linked List posted this gem: https://twitter.com/joshbloch/status/583813919019573248

My favorite on the idea of having a linked list where the node is first class in your code, is almost precisely the problem. You rarely want/need to work at that level. In a very real sense, objects that have other objects are already trees of data. Many can back reference, such that then you have a graph.

And then there is the joy of trying to use matrix operations to work with graphs. You can do some powerful things, but at that point, you almost certainly want the matrix to be the abstraction.

Excited to see someone come up with good things in this idea. I retain very serious doubts that I want a singular model for my data.

Re: The hunt for the missing data type

#30

Post by vonwoodson »

jes5199 wrote: post #22
gilleain wrote: post #19

Earlier quoted context omitted.

What do you mean by "textual graph literal"?

Textual array literal: [1,2,3] Textual dict literal: {"a": 1} Textual graph literal: ???

Textual graph literal: {"a->b", "b->c", "c->a"}

Thinking about the programming language DOT https://en.wikipedia.org/wiki/DOT_(graph_description_languag...

This may be an effective way to express these graphs.

Post reply on HN