Re:One Way to Represent Things
by hiker on Thursday February 25, 2021 @06:45AM
(#26261900)
If the focus is on finite data structures only and the equivalence relation is "are the types isomorphic", then each type is isomorphic to the ordinary generating functor with some coefficients C : N->N:
For example list has coefficients Cn = {1,1,1,1...}
and binary trees have coefficients the Catalan numbers {1,1,2,5,14,42,132,429,...}.Computing those coefficients from a type definition is not always trivial though (see the symbolic method http://algo.inria.fr/flajolet/Publications/AnaCombi/book.pdf).
This can be extended to infinite data structures too by switching the natural numbers to ordinal numbers in the ogf definition.