🚀 go-pugleaf

In article 5378@beaver.cs.washington.edu, jon@cs.washington.edu (Jon Jacky) writes:
>This generic schema summarizes some techniques I've seen.  You don't need to
>bother with free types, and you don't need recursive data structures.  Remember
>that any graph composed of nodes and arcs can be modelled by a relation.  A
>tree is just a special case:
>
>	+--Tree[Node]---------------------------
>	|  nodes: P Node
>	|  root: Node
>	|  parent: Node -+> Node
>	|  children: Node <-> Node
>	+---------------------------
>	|  root e nodes
>	|  dom parent U ran parent = nodes	
>	|  dom parent = nodes \ {root}
>	|  children = parent~
>	|  parent+ \cap id = empty
>	+--------------------------------------
>
>Parent is declared to be a function, not a relation, to say that a node can
>have only one parent.
>
>In order, the predicates say:
>
>- The root is a node.
>- All the nodes are connected, and everything that is connected is in nodes.
>- Every node except the root has a parent.
>- The children relation is just the inverse of the parent function.
>- There aren't any cycles - no node is its own ancestor.   This is expressed
>  by saying the transitive closure of parent doesn't intersect the identity
>  function.  
>
>I think that does it.

No.  In the general case the ordering of the subtrees rooted at a given node
is significant.  At the very least children would have to have the type
Node -> seq Node.  

	Chris Flatters
	cflatter@nrao.edu