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

61–70 of 259 posts

Re: The hunt for the missing data type

#61

Post by boothby »

tlb wrote: post #10
pizlonator wrote: post #2

I would claim that object oriented languages are a syntax, semantics and type system for graphs. Objects are nodes. Fields are edges. The object graph is the heap. So your whole program state is a graph.

A limitation is that you can only have one such graph in the program. So any graph algorithm that returns a graph, or uses another graph during the computation, doesn't fit.

Don't fall for the abstraction! Mathematically speaking, if you have graphs G1 and G2; you can make another graph H with nodes {G1, G2} and edges {(G1, G2)} and nothing goes wrong. You can definitely view your whole operating system as a graph; it doesn't invalidate having a program running which processes graphs.

Re: The hunt for the missing data type

#63

Post by at_a_remove »

Hrm. This reminds me of a thought I had about, for the lack of a better term, "groups" in Python. Each data type has a property which is paramount and more or less defines the type.

Lists are ordered. The tuple is immutable. The dict is keyed. The set is unique. (But there are some overlaps: dicts are both keyed and their keys are unique.)

And I thought, what if you had a group where you could make it immutable or mutable, ordered or not-ordered, where the value was a key to something else (or not), and so on? But then I saw the weird edge cases and the explosions of complexity. Some combinations of these attributes are less appealing than others.

Re: The hunt for the missing data type

#64

Post by JonChesterfield »

I needed a directed graph yesterday. I gave the nodes integer ids by appending them to an arena, then used a hashtable from integer to vector of integer. Iterating over it involves a set of integers to track which nodes have already been visited.

Deduplicating nodes on insert into the area was more hassle than cobbling together the graph structure out of a hashtable and a vector.

Maybe one reason against putting graphs in the standard library is they're easily put together from more common structures for whatever special case you have in mind.

Re: The hunt for the missing data type

#65

Post by qazxcvbnm »

This reminds me of my quest to find the proper method to model what I've termed 'large types' in an ideal language.

As is well known, algebraic data types as commonly found, consist of sums of products, yet a great deal of useful types are larger than that; some hopefully illustrative examples include:

1) the type of subsets of another type would be 2^X (hopefully demonstrating what I mean by 'large'ness);

2) in practical languages like TypeScript, the 'Partial' of a product type A x B x C would be (1 + A) x (1 + B) x (1 + C);

3) data structures in general, as a term amenable to some certain set of operations, when needing to be represented for performance reasons e.g. a) union-find structures (quotients?); b) a list of words and their inverted indexes for searching; c) a sorted list

Reading more about type modelling, and learning of the disagreements in how even basic things like quotients ought to be represented as types, I've since resigned to an understanding of this as an unsolved problem, and relegated the modelling the kitchen sinks of types with the kitchen sink of types - i.e. the function type (curbed with suitable type constraints upon the signature - from an index type to a suitable base type) - after all, its power and province being the irreducible kernel of type polymorphism, shadow over Church's types, original sin against type decidability.

Re: The hunt for the missing data type

#66

Post by boothby »

bevekspldnw wrote: post #62

Was seriously hoping at the start that article would reveal some secret easy solution to all my problems…only to learn there are none. :’(

I take solace in such findings. I learned that my quest was ill-conceived, and I abandoned it; I should be glad that I'm no longer searching for what cannot be found.

Re: The hunt for the missing data type

#67

Post by andoando »

qazxcvbnm wrote: post #65

This reminds me of my quest to find the proper method to model what I've termed 'large types' in an ideal language. As is well known, algebraic data types as commonly found, consist of sums of products, yet a great deal of useful types are larger than that; some hopefully illustrative examples include: 1) the type of subsets of another type would be 2^X (hopefully demonstrating what I mean by 'large'ness); 2) in prac…

I've been thinking about something like this for the last 3 years. However, I can't find a practical reason for it, even though I am sure there are.

Re: The hunt for the missing data type

#68

Post by aebtebeten »

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…

https://lobste.rs/s/uhmhum/hunt_for_missing_data_type#c_1na1...

> matrix multiplication and permanents are known to be non-cheap to compute, requiring worse-than-quadratic time! So any sort of good graph algorithm must dig deeper and be more specialized for the task at hand

Re: The hunt for the missing data type

#69

Post by DSMan195276 »

obi1kenobi wrote: post #31
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…

Two problems I see here, based on the research I've done in high-performance graph algorithms: - It's hard to find a "good-enough" graph implementation. The best hashtable is only a handful of percent better than the built-in ones. The best graph impl is 1000x or more better than any generic built-in one could be, so there's much more incentive to specialize (and people already specialize hashtables for just a handfu…

> The baseline complexity level of implementing a reasonable hashtable is fairly high, even if for a small dataset.

I would disagree with this, it's actually really easy to make one if you're willing to do away with many features (which aren't essential, but provide performance benefits). Implementing one is just something you never have to do in most modern languages.

Re: The hunt for the missing data type

#70

Post by gue5t »

qazxcvbnm wrote: post #65

This reminds me of my quest to find the proper method to model what I've termed 'large types' in an ideal language. As is well known, algebraic data types as commonly found, consist of sums of products, yet a great deal of useful types are larger than that; some hopefully illustrative examples include: 1) the type of subsets of another type would be 2^X (hopefully demonstrating what I mean by 'large'ness); 2) in prac…

These types don't seem to escape the scope of what can be described with algebraic types, but the relationships between them seem like you're looking for a notion of type-level functions: subset ≡ X => 2^X, partial ≡ A×B => (A+1)×partial(B)
Post reply on HN