cantor-pairing-0.2.0.0: Convert data to and from a natural number representation

Safe HaskellNone
LanguageHaskell2010

Cantor

Description

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

Recursive example

This should work nicely even with simple inductive types:

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

instance Cantor a => Cantor (Tree a)

Finite example

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

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

instance Cantor Color
instance Finite Color

Mutually-recursive types

If you have mutually-recursive types, unfortunately you'll need to manually specify the cardinality for now, but you can still get the to/from encodings for free:

data Foo = FooNil | Foo Bool Bar deriving (Generic,Show)
data Bar = BarNil | Bar Bool Foo deriving (Generic,Show)

instance Cantor Foo where
  cardinality = Countable
instance Cantor Bar
Synopsis

Documentation

cantorEnumeration :: Cantor a => [a] Source #

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

>>> take 5 cantorEnumeration :: [Data.IntSet.IntSet]
[fromList [],fromList [0],fromList [1],fromList [0,1],fromList [2]]

data Cardinality Source #

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

Countable 
Instances
Eq Cardinality Source # 
Instance details

Defined in Cantor

Ord Cardinality Source # 
Instance details

Defined in Cantor

Show Cardinality Source # 
Instance details

Defined in Cantor

Generic Cardinality Source # 
Instance details

Defined in Cantor

Associated Types

type Rep Cardinality :: Type -> Type #

type Rep Cardinality Source # 
Instance details

Defined in Cantor

pattern Finite :: Integer -> Cardinality Source #

Finite cardinality.

class Cantor a where Source #

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 Source #

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

toCantor :: Integer -> a Source #

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

fromCantor :: a -> Integer Source #

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

Instances
Cantor Bool Source # 
Instance details

Defined in Cantor

Cantor Char Source # 
Instance details

Defined in Cantor

Cantor Int Source # 
Instance details

Defined in Cantor

Cantor Int8 Source # 
Instance details

Defined in Cantor

Cantor Int16 Source # 
Instance details

Defined in Cantor

Cantor Int32 Source # 
Instance details

Defined in Cantor

Cantor Int64 Source # 
Instance details

Defined in Cantor

Cantor Integer Source # 
Instance details

Defined in Cantor

Cantor Natural Source # 
Instance details

Defined in Cantor

Cantor Word Source # 
Instance details

Defined in Cantor

Cantor Word8 Source # 
Instance details

Defined in Cantor

Cantor Word16 Source # 
Instance details

Defined in Cantor

Cantor Word32 Source # 
Instance details

Defined in Cantor

Cantor Word64 Source # 
Instance details

Defined in Cantor

Cantor () Source # 
Instance details

Defined in Cantor

Cantor Void Source # 
Instance details

Defined in Cantor

Cantor IntSet Source # 
Instance details

Defined in Cantor

Cantor a => Cantor [a] Source # 
Instance details

Defined in Cantor

Cantor a => Cantor (Maybe a) Source # 
Instance details

Defined in Cantor

Cantor a => Cantor (Min a) Source # 
Instance details

Defined in Cantor

Cantor a => Cantor (Max a) Source # 
Instance details

Defined in Cantor

Cantor a => Cantor (First a) Source # 
Instance details

Defined in Cantor

Cantor a => Cantor (Last a) Source # 
Instance details

Defined in Cantor

Cantor a => Cantor (Option a) Source # 
Instance details

Defined in Cantor

Cantor a => Cantor (Identity a) Source # 
Instance details

Defined in Cantor

Cantor a => Cantor (Sum a) Source # 
Instance details

Defined in Cantor

Cantor a => Cantor (Product a) Source # 
Instance details

Defined in Cantor

Cantor a => Cantor (Seq a) Source # 
Instance details

Defined in Cantor

(Ord a, Finite a) => Cantor (Set a) Source # 
Instance details

Defined in Cantor

(Finite a, Cantor b) => Cantor (a -> b) Source # 
Instance details

Defined in Cantor

(Cantor a, Cantor b) => Cantor (Either a b) Source # 
Instance details

Defined in Cantor

(Cantor a, Cantor b) => Cantor (a, b) Source # 
Instance details

Defined in Cantor

(Cantor a, Cantor b) => Cantor (Arg a b) Source # 
Instance details

Defined in Cantor

Cantor (Proxy a) Source # 
Instance details

Defined in Cantor

(Cantor a, Cantor b, Cantor c) => Cantor (a, b, c) Source # 
Instance details

Defined in Cantor

Methods

cardinality :: Cardinality Source #

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

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

Cantor a => Cantor (Const a b) Source # 
Instance details

Defined in Cantor

(Cantor a, Cantor b, Cantor c, Cantor d) => Cantor (a, b, c, d) Source # 
Instance details

Defined in Cantor

Methods

cardinality :: Cardinality Source #

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

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

(Cantor a, Cantor b, Cantor c, Cantor d, Cantor e) => Cantor (a, b, c, d, e) Source # 
Instance details

Defined in Cantor

Methods

cardinality :: Cardinality Source #

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

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

(Cantor a, Cantor b, Cantor c, Cantor d, Cantor e, Cantor f) => Cantor (a, b, c, d, e, f) Source # 
Instance details

Defined in Cantor

Methods

cardinality :: Cardinality Source #

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

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

(Cantor a, Cantor b, Cantor c, Cantor d, Cantor e, Cantor f, Cantor g) => Cantor (a, b, c, d, e, f, g) Source # 
Instance details

Defined in Cantor

Methods

cardinality :: Cardinality Source #

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

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

class Cantor a => Finite a Source #

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

Instances
Finite Bool Source # 
Instance details

Defined in Cantor

Methods

fCardinality' :: Huge

Finite Char Source # 
Instance details

Defined in Cantor

Methods

fCardinality' :: Huge

Finite Int Source # 
Instance details

Defined in Cantor

Methods

fCardinality' :: Huge

Finite Int8 Source # 
Instance details

Defined in Cantor

Methods

fCardinality' :: Huge

Finite Int16 Source # 
Instance details

Defined in Cantor

Methods

fCardinality' :: Huge

Finite Int32 Source # 
Instance details

Defined in Cantor

Methods

fCardinality' :: Huge

Finite Int64 Source # 
Instance details

Defined in Cantor

Methods

fCardinality' :: Huge

Finite Word Source # 
Instance details

Defined in Cantor

Methods

fCardinality' :: Huge

Finite Word8 Source # 
Instance details

Defined in Cantor

Methods

fCardinality' :: Huge

Finite Word16 Source # 
Instance details

Defined in Cantor

Methods

fCardinality' :: Huge

Finite Word32 Source # 
Instance details

Defined in Cantor

Methods

fCardinality' :: Huge

Finite Word64 Source # 
Instance details

Defined in Cantor

Methods

fCardinality' :: Huge

Finite () Source # 
Instance details

Defined in Cantor

Methods

fCardinality' :: Huge

Finite Void Source # 
Instance details

Defined in Cantor

Methods

fCardinality' :: Huge

Finite IntSet Source # 
Instance details

Defined in Cantor

Methods

fCardinality' :: Huge

Finite a => Finite (Maybe a) Source # 
Instance details

Defined in Cantor

Methods

fCardinality' :: Huge

Finite a => Finite (Min a) Source # 
Instance details

Defined in Cantor

Methods

fCardinality' :: Huge

Finite a => Finite (Max a) Source # 
Instance details

Defined in Cantor

Methods

fCardinality' :: Huge

Finite a => Finite (First a) Source # 
Instance details

Defined in Cantor

Methods

fCardinality' :: Huge

Finite a => Finite (Last a) Source # 
Instance details

Defined in Cantor

Methods

fCardinality' :: Huge

Finite a => Finite (Option a) Source # 
Instance details

Defined in Cantor

Methods

fCardinality' :: Huge

Finite a => Finite (Identity a) Source # 
Instance details

Defined in Cantor

Methods

fCardinality' :: Huge

Finite a => Finite (Sum a) Source # 
Instance details

Defined in Cantor

Methods

fCardinality' :: Huge

Finite a => Finite (Product a) Source # 
Instance details

Defined in Cantor

Methods

fCardinality' :: Huge

(Ord a, Finite a) => Finite (Set a) Source # 
Instance details

Defined in Cantor

Methods

fCardinality' :: Huge

(Finite a, Finite b) => Finite (a -> b) Source # 
Instance details

Defined in Cantor

Methods

fCardinality' :: Huge

(Finite a, Finite b) => Finite (Either a b) Source # 
Instance details

Defined in Cantor

Methods

fCardinality' :: Huge

(Finite a, Finite b) => Finite (a, b) Source # 
Instance details

Defined in Cantor

Methods

fCardinality' :: Huge

(Finite a, Finite b) => Finite (Arg a b) Source # 
Instance details

Defined in Cantor

Methods

fCardinality' :: Huge

Finite (Proxy a) Source # 
Instance details

Defined in Cantor

Methods

fCardinality' :: Huge

(Finite a, Finite b, Finite c) => Finite (a, b, c) Source # 
Instance details

Defined in Cantor

Methods

fCardinality' :: Huge

Finite a => Finite (Const a b) Source # 
Instance details

Defined in Cantor

Methods

fCardinality' :: Huge

(Finite a, Finite b, Finite c, Finite d) => Finite (a, b, c, d) Source # 
Instance details

Defined in Cantor

Methods

fCardinality' :: Huge

(Finite a, Finite b, Finite c, Finite d, Finite e) => Finite (a, b, c, d, e) Source # 
Instance details

Defined in Cantor

Methods

fCardinality' :: Huge

(Finite a, Finite b, Finite c, Finite d, Finite e, Finite f) => Finite (a, b, c, d, e, f) Source # 
Instance details

Defined in Cantor

Methods

fCardinality' :: Huge

(Finite a, Finite b, Finite c, Finite d, Finite e, Finite f, Finite g) => Finite (a, b, c, d, e, f, g) Source # 
Instance details

Defined in Cantor

Methods

fCardinality' :: Huge

fCardinality :: forall a. Finite a => Integer Source #

Cardinality of a finite type.