Computer Science – Symbolic Computation
Scientific paper
2008-08-06
Computer Science
Symbolic Computation
unpublished draft
Scientific paper
Using specializations of unfold and fold on a generic tree data type we derive unranking and ranking functions providing natural number encodings for various Hereditarily Finite datatypes. In this context, we interpret unranking operations as instances of a generic anamorphism and ranking operations as instances of the corresponding catamorphism. Starting with Ackerman's Encoding from Hereditarily Finite Sets to Natural Numbers we define pairings and tuple encodings that provide building blocks for a theory of Hereditarily Finite Functions. The more difficult problem of ranking and unranking Hereditarily Finite Permutations is then tackled using Lehmer codes and factoradics. 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/fFUN.zip}. Keywords: ranking/unranking, pairing/tupling functions, Ackermann encoding, hereditarily finite sets, hereditarily finite functions, permutations and factoradics, computational mathematics, Haskell data representations
No associations
LandOfFree
Ranking Catamorphisms and Unranking Anamorphisms on Hereditarily Finite Datatypes 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 Ranking Catamorphisms and Unranking Anamorphisms on Hereditarily Finite Datatypes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Ranking Catamorphisms and Unranking Anamorphisms on Hereditarily Finite Datatypes will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-27409