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

[kthielen]

> 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

You also need "inductive" recursive types to represent lists and trees, in addition to sums and products.

One way of representing the type of a list of T is like:

mu X.1+T*X

(Hence sum and product types, but also inductive or "least fixed point" recursion.)

But you can also use "coinductive" recursive types to represent "processes" (or "greatest fixed point" recursion) with almost the same notation:

nu X.1+T*X

This represents a FSM which at any point yields either a termination (the "1" on the left side of the recursive sum) or a value and a continuation (the "T" in "T*X" is the value and the "X" in "T*X" is the continuation).

This doesn't answer every question about graph representation, obviously, but it's a useful tool for attacking some graph problems you'd like to represent "syntactically" as you say (though you have to think in terms of "coinduction" instead of "induction" e.g. bisimilarity instead of equality).

[nickpsecurity]

That’s a neat idea. The other side of it might be expressiveness.

The more expressive constructs are usually more productive and concise. The less expressive constructs are usually easier to optimize or analyze with a machine. The old rule, like in LANGSEC, is to pick the least-expressive option that works. Some people also develop transforming code (eg netaprogramming) to let you write highly-expressive code that generates correct, low-expressiveness code.

[schindlabua]

I like thinking of this concept via free constructions.

As is somewhat commonly known the free Monoid is the List type; monoids are not commutative so we get a sense of "direction", like a list has a start and an end.

If we add commutativity and look at free groups, we find they are equivalent to multisets.

If we take associativity away from monoids and look at free semigroups, we get binary finger trees, I think?

In some sense removing constraints from the binary operator results in more general free types. Would be interesting to find what free construction makes digraphs but I have to bounce.