Hacker News Reader

Comment by 4ad | Hacker News Reader

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.

View on HN

> 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

> 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.

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.

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.

In what sense graphs require mutation?

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.

Reply on news.ycombinator.com