Declarative Combinatorics: Isomorphisms, Hylomorphisms and Hereditarily Finite Data Types in Haskell

Details Declarative Combinatorics: Isomorphisms, Hylomorphisms and Hereditarily Finite Data Types in Haskell Declarative Combinatorics: Isomorphisms, Hylomorphisms and Hereditarily Finite Data Types in Haskell

2008-08-21

arxiv.org/abs/0808.2953v4

Computer Science

Programming Languages

unpublished draft, revision 3, added various new encodings, with focus on primes and multisets, now 104 pages

Scientific paper

This paper is an exploration in a functional programming framework of {\em isomorphisms} between elementary data types (natural numbers, sets, multisets, finite functions, permutations binary decision diagrams, graphs, hypergraphs, parenthesis languages, dyadic rationals, primes, DNA sequences etc.) and their extension to hereditarily finite universes through {\em hylomorphisms} derived from {\em ranking/unranking} and {\em pairing/unpairing} operations. An embedded higher order {\em 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 instances. The paper covers 59 data types and, through the use of the embedded combinator language, provides 3540 distinct bijective transformations between them. The self-contained source code of the paper, as generated from a literate Haskell program, is available at \url{http://logic.csci.unt.edu/tarau/research/2008/fISO.zip}. {\bf Keywords}: Haskell data representations, data type isomorphisms, declarative combinatorics, computational mathematics, Ackermann encoding, G\"{o}del numberings, arithmetization, ranking/unranking, hereditarily finite sets, functions and permutations, encodings of binary decision diagrams, dyadic rationals, DNA encodings

Affiliated with

Also associated with

No associations

Rating

Declarative Combinatorics: Isomorphisms, Hylomorphisms and Hereditarily Finite Data Types in Haskell does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Declarative Combinatorics: Isomorphisms, Hylomorphisms and Hereditarily Finite Data Types in Haskell, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Declarative Combinatorics: Isomorphisms, Hylomorphisms and Hereditarily Finite Data Types in Haskell will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-219835