5 ms·

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 gra

by 4ad 3y ago

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.

boothby 3y ago
I disagree: trees are connected graphs with n nodes and n-1 edges. They're graphs with a special structure that is highly exploitable for performance gains, but they're graphs.
zokier 3y ago
In what sense graphs require mutation?
- joshlemer 3y ago
  I think maybe they're talking about how, in order to create a data structure where two nodes contain a reference (edge) to each other, you have to resort to mutation. i.e. you have to create A, then B with reference to A, then mutate A to refer to B, or you have to create B, then A with reference to B, then mutate B to refer to A. Though this ignores that there are other ways to represent graphs, such as adjacency matrices, etc.
harporoeder 3y ago
Even with direct mutual references between some node type this can be represented in a lazy functional language such as Haskell pretty easily without mutation.
bigbillheck 3y ago
> Why don't we have graphs ... in Rust? You might have missed this from the article but: https://docs.rs/petgraph/latest/petgraph/index.html https://docs.rs/petgraph/latest/petgraph/index.html > Because graphs require mutation (respectively break linearity). I don't think this is actually the case. Graph nodes go in one container (`Vec` or `HashMap` or `BTreeMap`), and the edges go in another container (`HashMap` or `BTreeMap`). The object in which you store the node only needs to know what its name is, you can let something else know what its neighbors are.

by 4ad 3y ago

boothby 3y ago

I disagree: trees are connected graphs with n nodes and n-1 edges. They're graphs with a special structure that is highly exploitable for performance gains, but they're graphs.

zokier 3y ago

In what sense graphs require mutation?

joshlemer 3y ago
I think maybe they're talking about how, in order to create a data structure where two nodes contain a reference (edge) to each other, you have to resort to mutation. i.e. you have to create A, then B with reference to A, then mutate A to refer to B, or you have to create B, then A with reference to B, then mutate B to refer to A. Though this ignores that there are other ways to represent graphs, such as adjacency matrices, etc.

harporoeder 3y ago

Even with direct mutual references between some node type this can be represented in a lazy functional language such as Haskell pretty easily without mutation.

bigbillheck 3y ago

> Why don't we have graphs ... in Rust? You might have missed this from the article but: https://docs.rs/petgraph/latest/petgraph/index.html https://docs.rs/petgraph/latest/petgraph/index.html > Because graphs require mutation (respectively break linearity). I don't think this is actually the case. Graph nodes go in one container (`Vec` or `HashMap` or `BTreeMap`), and the edges go in another container (`HashMap` or `BTreeMap`). The object in which you store the node only needs to know what its name is, you can let something else know what its neighbors are.