1 Summary Substructural Functional Programming

Graph rewriting is a suitable technique to implement lazy functional languages efficiently.[1] A computation in a graph rewrite system is specified by a set of graph rewrite rules that are used to rewrite a given initial graph to its final result. The intermediate graphs are called data graphs. Consider the following facts: – Functional expressions can express any data graph. – During graph rewriting cyclic structures are preserved. More precisely: if two arcs in the data graph point to the same node A, they will point to the same node B until they will be garbage-collected (A and B might be the same). This could be a background for efficient implementation of graph algorithms, but at least two features are missing: – An expression should be able to distinguish that two arcs in the graph point to the same node or not. This is the comparing feature. – Suppose that we would like to alter a graph a little bit, and we know that the old value will not be used any more. In this case the graph could be destructively update