[seqfan] article by Paul Taurau on bijections to naturals

Georgi Guninski guninski at guninski.com
Tue Feb 23 09:09:26 CET 2010

Probably this is well known:

Isomorphic Data Encodings and their
Generalization to Hylomorphisms on
   Hereditarily Finite Data Types
               Paul Tarau

Haskell code: http://logic.csci.unt.edu/tarau/research/2009/fISO.zip

158 pages, many figures and examples.

The author gives bijections N <=>:
Finite sets
Finite multisets
bijective base-k

For some types the author gives more than one bijection and this may be source for permutations of the naturals:

Experimentally "casting" the complete graph on n nodes to a(n) in haskell:

*ISO> let cgr n = [(x,y) | x <- [0 .. n - 1],y <- [0..n-1],x<y] --complete graph on n vertices
*ISO> let gra=[cgr i | i <- [1..6]]
*ISO> gra
*ISO> [as nat graph i | i<-gra] -- graph to N

More information about the SeqFan mailing list