71–80 of 259 posts
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…
So whoever solve the problem for generic graph drawing will have the ability or the insight to implement this too.
Ok, trees are not graphs but they are very related, and algebraic data types are trees, so they are ubiquitous in functional programming. Why don't we have graphs in FP (or in Rust)? Because graphs require mutation (respectively break linearity). Why don't we have graphs in imperative languages? Perhaps because very few imperative languages have ADTs? Just a thought.
In what sense graphs require mutation?
Though this ignores that there are other ways to represent graphs, such as adjacency matrices, etc.
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.
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…
Data structures are specialized graph representations. The source code you write is in a specialized graph representation. For the overwhelming majority of programmers, the fact that something can be viewed as a graph is much like saying "oh well that file is just a really long sequence of bits, so it's effectively an integer." It's not wrong, but is it useful?
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…
For example, I'd like to program against a sequence abstraction. When sort is applied to it, I hope it's a vector. When slice or splice, I hope it's some sort of linked structure. Size is as cheap as empty for the vector but much more expensive for a linked list.
It should be possible to determine a reasonable data representation statically based on the operations and control flow graph, inserting conversions where the optimal choice is different.
The drawback of course is that people write different programs for different data structures. Knowing what things are cheap and what aren't guides the design. There's also a relinquishing of control implied by letting the compiler choose for you that people may dislike.
As an anecdote for the latter, clojure uses vectors for lambda arguments. I thought that was silly since it's a lisp that mostly works in terms of seq abstractions, why not have the compiler choose based on what you do with the sequence? The professional clojure devs I was talking to really didn't like that idea.
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)
Certainly it is possible to represent each specific case as some algebraic type; but beyond trivial cases, I find that when I need such of these types, quickly I discover that there are myriad ways to express them, none of them uniquely natural, unlike the way a sum of products type (and its terms) can be pretty much unambiguously drawn from a specification.
This matters especially when e.g. I need to evolve my types in a data migration.
Earlier quoted context omitted.
Same - DOT is a great way to go from zero to functional in near minimal time. It's also pretty trivial to generate since it's not order dependent, which is great for lightweight automation. Fine-tuning layout can be a real hassle though, sadly. I haven't found any quick tools for that yet.
The way I approach fine-tuning DOT layout is to add subgroups where it seems appropriate, add a 1px border for the subgroup and see where the layout engine is situating it next to other nearby vertices/edges. Sometimes I may have to put a border around a few subgroups, then attempt to adjust size of vertices and entire area to nudge it to a local minima. Note: I don't attempt to adjust the size of the subgroups, I'm…
I am especially interested in syntax suitable to be used in creating something to input into https://www.viz-js.com and creation of SVGs with embedded hyperlinks.
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 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.
It's another instance of the phenomenon which Strousroup noticed: 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.