Skip to content

Coalgebra Printing

In addition to functors, we also need to be able to print coalgebras from the internal encoding into a parseable textual representation.

Coalgebras are internally represented as:

  1. An array for F1 values.
  2. An array of edges (from, label, to).
  3. A symbol table for states in the first sort

1 and 2 are part of the Encoding data structure.

Implementation Sketch

I'm envisioning something like the following, but haven't worked out the details:

Analogous to the ParseMorphism class, we introduce a new class PrintMorphism that every functor is expected to implement:

class PrintMorphism f where
  printMorphismPoint :: F1 f -> [(Label f, Builder)] -> Builder

where Builder is the usual Data.Text.Builder and the arguments are the f1 value and (already printed) successors for a particular state in the coalgebra encoding.

Then, a function

printState :: Vector (F1 f) -> Vector [(Label f, State)] -> State -> Builder

can recursively print the whole graph. The second argument Vector [(Label f, State)] is an adjacency list representation of the encoding for easier successor lookup.

Note that the graph should contain no cycles except for back-edges to the first sort. Also, we can assume that the transitive successor structure of a single named state has the shape of a tree except for the leaves which have the aforementioned outgoing back-edges. This means that we don't need to worry about duplicating internal states (for now).