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