Complex Systems

“Everything Is Everything” Revisited: Shapeshifting Data Types with Isomorphisms and Hylomorphisms Download PDF

Paul Tarau
Department of Computer Science and Engineering
University of North Texas
Denton, TX 76203-6886, USA

Abstract

This paper is an exploration of isomorphisms between elementary data types (e.g., natural numbers, sets, finite functions, graphs, hypergraphs) and their extension to hereditarily finite universes through hylomorphisms derived from ranking/unranking and pairing/unpairing operations. An embedded higher order combinator language provides any-to-any encodings automatically. 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 succinct data representations and the generation of random instances.