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:
- An array for
F1
values. - An array of edges
(from, label, to)
. - 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).