Cantor

Cantor pairing gives us an isomorphism between a single natural number and pairs of natural numbers. This package provides a modern API to this functionality using GHC generics, allowing the encoding of arbitrary combinations of finite or countably infinite types in natural number form.

As a user, all you need to do is derive generic and get the instances for free.

Example

import GHC.Generics
import Cantor

data MyType = MyType {
    value1 :: [ Maybe Bool ]
  , value2 :: Integer
  } deriving (Generic)

instance Cantor MyType

This should work nicely even with simple inductive types:

Recursive example

data Tree a = Leaf | Branch (Tree a) a (Tree a) deriving (Generic)

instance Cantor a => Cantor (Tree a)

If your type is finite, you can specify this by deriving the Finite typeclass, which is a subclass of Cantor:

Finite example

data Color = Red | Green | Blue deriving (Generic)

instance Cantor Color
instance Finite Color

Documentation

cantorEnumeration :: Cantor a => [a]

Enumerates all values of a type by mapping toCantor over the naturals or finite subset of naturals with the correct cardinality.

If the cardinality of the type is large and finite, (e.g., IntSet), you will need to try fixing the amount of items you want instead like toCantor IntSet $ [ 0 .. 10 ]. This is unfortunately necessary because even though the list is computed lazily in cantorEnumeration, its *size* is not, and the size of IntSet is a *very* large number which is not feasible to compute even on a modern system (it has more than 200k terabytes of digits!). Note that if you defer to using even larger types like Integer which have true non-finite cardinality instead of finite approximations like Int@, you will naturally tend to avoid this problem.

data Cardinality

Cardinality can be either Finite or Countable. Countable cardinality entails that a type has the same cardinality as the natural numbers. Note that not all infinite types are countable: for example, Natural -> Natural is an infinite type, but it is not countably infinite; the basic intuition is that there is no possible way to enumerate all values of type Natural -> Natural without "skipping" almost all of them. This is in contrast to the naturals, where despite their being infinite, we can trivially (by definition, in fact!) enumerate all of them without skipping any.

Constructors

Finite Integer

Countable

Instances

Eq Cardinality

Defined in Cantor

Methods

(==) :: Cardinality -> Cardinality -> Bool

(/=) :: Cardinality -> Cardinality -> Bool

Ord Cardinality

Defined in Cantor

Methods

compare :: Cardinality -> Cardinality -> Ordering

(<) :: Cardinality -> Cardinality -> Bool

(<=) :: Cardinality -> Cardinality -> Bool

(>) :: Cardinality -> Cardinality -> Bool

(>=) :: Cardinality -> Cardinality -> Bool

max :: Cardinality -> Cardinality -> Cardinality

min :: Cardinality -> Cardinality -> Cardinality

Show Cardinality

Defined in Cantor

Methods

showsPrec :: Int -> Cardinality -> ShowS

show :: Cardinality -> String

showList :: [Cardinality] -> ShowS

Generic Cardinality

Defined in Cantor

Associated Types

type Rep Cardinality :: Type -> Type

Methods

from :: Cardinality -> Rep Cardinality x

to :: Rep Cardinality x -> Cardinality

type Rep Cardinality

Defined in Cantor

type Rep Cardinality = D1 (MetaData "Cardinality" "Cantor" "cantor-pairing-0.1.1.0-FBbMe1kbiImEcWdMYyX8cH" False) (C1 (MetaCons "Finite" PrefixI False) (S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 Integer)) :+: C1 (MetaCons "Countable" PrefixI False) (U1 :: Type -> Type))

class Cantor a where

The Cantor class gives a way to convert a type to and from the natural numbers, as well as specifies the cardinality of the type.

Minimal complete definition

Nothing

Methods

cardinality :: Cardinality

cardinality :: GCantor a (Rep a) => Cardinality

toCantor :: Integer -> a

toCantor :: (Generic a, GCantor a (Rep a)) => Integer -> a

fromCantor :: a -> Integer

fromCantor :: (Generic a, GCantor a (Rep a)) => a -> Integer

Instances

Cantor Bool

Defined in Cantor

Methods

cardinality :: Cardinality

toCantor :: Integer -> Bool

fromCantor :: Bool -> Integer

Cantor Char

Defined in Cantor

Methods

cardinality :: Cardinality

toCantor :: Integer -> Char

fromCantor :: Char -> Integer

Cantor Int

Defined in Cantor

Methods

cardinality :: Cardinality

toCantor :: Integer -> Int

fromCantor :: Int -> Integer

Cantor Int8

Defined in Cantor

Methods

cardinality :: Cardinality

toCantor :: Integer -> Int8

fromCantor :: Int8 -> Integer

Cantor Int16

Defined in Cantor

Methods

cardinality :: Cardinality

toCantor :: Integer -> Int16

fromCantor :: Int16 -> Integer

Cantor Int32

Defined in Cantor

Methods

cardinality :: Cardinality

toCantor :: Integer -> Int32

fromCantor :: Int32 -> Integer

Cantor Int64

Defined in Cantor

Methods

cardinality :: Cardinality

toCantor :: Integer -> Int64

fromCantor :: Int64 -> Integer

Cantor Integer

Defined in Cantor

Methods

cardinality :: Cardinality

toCantor :: Integer -> Integer

fromCantor :: Integer -> Integer

Cantor Natural

Defined in Cantor

Methods

cardinality :: Cardinality

toCantor :: Integer -> Natural

fromCantor :: Natural -> Integer

Cantor Word

Defined in Cantor

Methods

cardinality :: Cardinality

toCantor :: Integer -> Word

fromCantor :: Word -> Integer

Cantor Word8

Defined in Cantor

Methods

cardinality :: Cardinality

toCantor :: Integer -> Word8

fromCantor :: Word8 -> Integer

Cantor Word16

Defined in Cantor

Methods

cardinality :: Cardinality

toCantor :: Integer -> Word16

fromCantor :: Word16 -> Integer

Cantor Word32

Defined in Cantor

Methods

cardinality :: Cardinality

toCantor :: Integer -> Word32

fromCantor :: Word32 -> Integer

Cantor Word64

Defined in Cantor

Methods

cardinality :: Cardinality

toCantor :: Integer -> Word64

fromCantor :: Word64 -> Integer

Cantor ()

Defined in Cantor

Methods

cardinality :: Cardinality

toCantor :: Integer -> ()

fromCantor :: () -> Integer

Cantor Void

Defined in Cantor

Methods

cardinality :: Cardinality

toCantor :: Integer -> Void

fromCantor :: Void -> Integer

Cantor IntSet

Defined in Cantor

Methods

cardinality :: Cardinality

toCantor :: Integer -> IntSet

fromCantor :: IntSet -> Integer

Cantor a => Cantor [a]

Defined in Cantor

Methods

cardinality :: Cardinality

toCantor :: Integer -> [a]

fromCantor :: [a] -> Integer

Cantor a => Cantor (Maybe a)

Defined in Cantor

Methods

cardinality :: Cardinality

toCantor :: Integer -> Maybe a

fromCantor :: Maybe a -> Integer

Cantor a => Cantor (Min a)

Defined in Cantor

Methods

cardinality :: Cardinality

toCantor :: Integer -> Min a

fromCantor :: Min a -> Integer

Cantor a => Cantor (Max a)

Defined in Cantor

Methods

cardinality :: Cardinality

toCantor :: Integer -> Max a

fromCantor :: Max a -> Integer

Cantor a => Cantor (First a)

Defined in Cantor

Methods

cardinality :: Cardinality

toCantor :: Integer -> First a

fromCantor :: First a -> Integer

Cantor a => Cantor (Last a)

Defined in Cantor

Methods

cardinality :: Cardinality

toCantor :: Integer -> Last a

fromCantor :: Last a -> Integer

Cantor a => Cantor (Option a)

Defined in Cantor

Methods

cardinality :: Cardinality

toCantor :: Integer -> Option a

fromCantor :: Option a -> Integer

Cantor a => Cantor (Identity a)

Defined in Cantor

Methods

cardinality :: Cardinality

toCantor :: Integer -> Identity a

fromCantor :: Identity a -> Integer

Cantor a => Cantor (Sum a)

Defined in Cantor

Methods

cardinality :: Cardinality

toCantor :: Integer -> Sum a

fromCantor :: Sum a -> Integer

Cantor a => Cantor (Product a)

Defined in Cantor

Methods

cardinality :: Cardinality

toCantor :: Integer -> Product a

fromCantor :: Product a -> Integer

Cantor a => Cantor (Seq a)

Defined in Cantor

Methods

cardinality :: Cardinality

toCantor :: Integer -> Seq a

fromCantor :: Seq a -> Integer

(Ord a, Finite a) => Cantor (Set a)

Defined in Cantor

Methods

cardinality :: Cardinality

toCantor :: Integer -> Set a

fromCantor :: Set a -> Integer

(Finite a, Cantor b) => Cantor (a -> b)

Defined in Cantor

Methods

cardinality :: Cardinality

toCantor :: Integer -> a -> b

fromCantor :: (a -> b) -> Integer

(Cantor a, Cantor b) => Cantor (Either a b)

Defined in Cantor

Methods

cardinality :: Cardinality

toCantor :: Integer -> Either a b

fromCantor :: Either a b -> Integer

(Cantor a, Cantor b) => Cantor (a, b)

Defined in Cantor

Methods

cardinality :: Cardinality

toCantor :: Integer -> (a, b)

fromCantor :: (a, b) -> Integer

(Cantor a, Cantor b) => Cantor (Arg a b)

Defined in Cantor

Methods

cardinality :: Cardinality

toCantor :: Integer -> Arg a b

fromCantor :: Arg a b -> Integer

Cantor (Proxy a)

Defined in Cantor

Methods

cardinality :: Cardinality

toCantor :: Integer -> Proxy a

fromCantor :: Proxy a -> Integer

(Cantor a, Cantor b, Cantor c) => Cantor (a, b, c)

Defined in Cantor

Methods

cardinality :: Cardinality

toCantor :: Integer -> (a, b, c)

fromCantor :: (a, b, c) -> Integer

Cantor a => Cantor (Const a b)

Defined in Cantor

Methods

cardinality :: Cardinality

toCantor :: Integer -> Const a b

fromCantor :: Const a b -> Integer

(Cantor a, Cantor b, Cantor c, Cantor d) => Cantor (a, b, c, d)

Defined in Cantor

Methods

cardinality :: Cardinality

toCantor :: Integer -> (a, b, c, d)

fromCantor :: (a, b, c, d) -> Integer

(Cantor a, Cantor b, Cantor c, Cantor d, Cantor e) => Cantor (a, b, c, d, e)

Defined in Cantor

Methods

cardinality :: Cardinality

toCantor :: Integer -> (a, b, c, d, e)

fromCantor :: (a, b, c, d, e) -> Integer

(Cantor a, Cantor b, Cantor c, Cantor d, Cantor e, Cantor f) => Cantor (a, b, c, d, e, f)

Defined in Cantor

Methods

cardinality :: Cardinality

toCantor :: Integer -> (a, b, c, d, e, f)

fromCantor :: (a, b, c, d, e, f) -> Integer

(Cantor a, Cantor b, Cantor c, Cantor d, Cantor e, Cantor f, Cantor g) => Cantor (a, b, c, d, e, f, g)

Defined in Cantor

Methods

cardinality :: Cardinality

toCantor :: Integer -> (a, b, c, d, e, f, g)

fromCantor :: (a, b, c, d, e, f, g) -> Integer

class Cantor a => Finite a where

The Finite typeclass simply entails that the Cardinality of the set is finite.

Minimal complete definition

Nothing

Methods

fCardinality :: Integer

Instances

Finite Bool

Defined in Cantor

Methods

fCardinality :: Integer

Finite Char

Defined in Cantor

Methods

fCardinality :: Integer

Finite Int

Defined in Cantor

Methods

fCardinality :: Integer

Finite Int8

Defined in Cantor

Methods

fCardinality :: Integer

Finite Int16

Defined in Cantor

Methods

fCardinality :: Integer

Finite Int32

Defined in Cantor

Methods

fCardinality :: Integer

Finite Int64

Defined in Cantor

Methods

fCardinality :: Integer

Finite Word

Defined in Cantor

Methods

fCardinality :: Integer

Finite Word8

Defined in Cantor

Methods

fCardinality :: Integer

Finite Word16

Defined in Cantor

Methods

fCardinality :: Integer

Finite Word32

Defined in Cantor

Methods

fCardinality :: Integer

Finite Word64

Defined in Cantor

Methods

fCardinality :: Integer

Finite ()

Defined in Cantor

Methods

fCardinality :: Integer

Finite Void

Defined in Cantor

Methods

fCardinality :: Integer

Finite IntSet

Defined in Cantor

Methods

fCardinality :: Integer

Finite a => Finite (Maybe a)

Defined in Cantor

Methods

fCardinality :: Integer

Finite a => Finite (Min a)

Defined in Cantor

Methods

fCardinality :: Integer

Finite a => Finite (Max a)

Defined in Cantor

Methods

fCardinality :: Integer

Finite a => Finite (First a)

Defined in Cantor

Methods

fCardinality :: Integer

Finite a => Finite (Last a)

Defined in Cantor

Methods

fCardinality :: Integer

Finite a => Finite (Option a)

Defined in Cantor

Methods

fCardinality :: Integer

Finite a => Finite (Identity a)

Defined in Cantor

Methods

fCardinality :: Integer

Finite a => Finite (Sum a)

Defined in Cantor

Methods

fCardinality :: Integer

Finite a => Finite (Product a)

Defined in Cantor

Methods

fCardinality :: Integer

(Ord a, Finite a) => Finite (Set a)

Defined in Cantor

Methods

fCardinality :: Integer

(Finite a, Finite b) => Finite (a -> b)

Defined in Cantor

Methods

fCardinality :: Integer

(Finite a, Finite b) => Finite (Either a b)

Defined in Cantor

Methods

fCardinality :: Integer

(Finite a, Finite b) => Finite (a, b)

Defined in Cantor

Methods

fCardinality :: Integer

(Finite a, Finite b) => Finite (Arg a b)

Defined in Cantor

Methods

fCardinality :: Integer

Finite (Proxy a)

Defined in Cantor

Methods

fCardinality :: Integer

(Finite a, Finite b, Finite c) => Finite (a, b, c)

Defined in Cantor

Methods

fCardinality :: Integer

Finite a => Finite (Const a b)

Defined in Cantor

Methods

fCardinality :: Integer

(Finite a, Finite b, Finite c, Finite d) => Finite (a, b, c, d)

Defined in Cantor

Methods

fCardinality :: Integer

(Finite a, Finite b, Finite c, Finite d, Finite e) => Finite (a, b, c, d, e)

Defined in Cantor

Methods

fCardinality :: Integer

(Finite a, Finite b, Finite c, Finite d, Finite e, Finite f) => Finite (a, b, c, d, e, f)

Defined in Cantor

Methods

fCardinality :: Integer

(Finite a, Finite b, Finite c, Finite d, Finite e, Finite f, Finite g) => Finite (a, b, c, d, e, f, g)

Defined in Cantor

Methods

fCardinality :: Integer