This paper is an exploration in a functional programming framework of isomorphisms between elementary data types (natural numbers, sets, multisets, finite functions, permutations binary decision diagrams, graphs, hypergraphs, parenthesis languages, dyadic rationals, DNA sequences etc.) and their extension to hereditary finite universes through hylomorphisms derived from ranking/unranking and pairing/unpairing operations. An embedded higher order combinator language provides any-to-any encodings automatically. Besides applications to experimental mathematics, a few examples of "free algorithms" obtained by transferring operations between data types are shown. Other applications range from stream iterators on combinatorial objects to self-delimiting codes, succinct data representations and generation of random instancs. The paper covers 47 data types and, through the use of the embedded combinator language, provides 2162 distinct bijective transformations between them.
In denotational semantics and functional programming, the terms monad morphism, monad layering, monad constructor, and monad transformer have by now accumulated 20 years of twisted history. The exchange between Eric Kidd and sigfpe about the probability monad prompted me to investigate this history
A. de Buitléir, M. Daly, M. Russell, und D. Heffernan. Trends in Functional Programming: 15th International
Symposium, TFP 2014, Soesterberg, The Netherlands, May
26-28, 2014. Revised Selected Papers, Volume 8843 von Lecture Notes in Computer Science, Springer International Publishing, (2015)
D. Brown, A. Garmendia-Doval, und J. McCall. Selected papers from the 2nd Scottish Functional
Programming Workshop (SFP00), Seite 27--38. Exeter, UK, UK, Intellect Books, (2000)
P. Hudak, J. Hughes, S. Jones, und P. Wadler. Proceedings of the third ACM SIGPLAN conference on History of programming languages, New York, NY, USA, ACM, (2007)
M. Hofmann, E. Kitzelmann, und U. Schmid. German Conference on Artificial Intelligence (KI'08), Volume 5243 von LNAI, Seite 78--86. Springer-Verlag, (2008)