# Cantor Tuples

Cantor pairs (and triplets, or tuples in general) are way to enumerate multi-dimensional spaces, similar to the Z curve. Unlike the Z curve, Cantor Tuples don’t preserve locality very well.

The idea is very simple: we trace a curve back and forth across the space until we’ve covered the whole thing. Here are the definitions we’ll be using below:

`type Dimensions = Int`

- How many
`Dimensions`

to work in

- How many
`type Range = Int`

- A bounded or unbounded
`Range`

of coordinates

- A bounded or unbounded
`range n = if n == 0 then [0..] else [0..n]`

- A way to enumerate a
`Range`

- A way to enumerate a
`type Point = [Int]`

- Storing
*lists*of coordinates rather than tuples lets us use any number of`Dimensions`

- Storing
`type Curve = [Point]`

- A
`Curve`

is a line traced through the space

- A
`data Shape = Shape {sDim :: Dimensions, sRange :: Range, sPred :: Point -> Bool}`

- We define a
`Shape`

using a*predicate*, deciding whether a`Point`

is in the`Shape`

or not

- We define a

## Axis-aligned `Curves`

The most obvious way to trace a `Curve`

across a
`Shape`

is
to start at `(0, 0)`

(which for our purposes will be the
*top* left of the images) and increase, say, the `x`

coordinate to get `(1, 0)`

, then `(2, 0)`

, etc.
until we exhaust the `Shape`

’s `Range`

, then
jump to `(0, 1)`

and do the same thing, and so on:

```
aaCurve :: Range -> Dimensions -> Curve
1 = [[x] | x <- range r]
aaCurve r = [x:xs | x <- range r, xs <- aaCurve r (n - 1)]
aaCurve r n
aaShape :: Shape -> Curve
Shape d r p) = filter p (aaCurve r d) aaShape (
```

If we use this to trace a black-to-white gradient across a square image, we get this:

### A Finite Example

Let’s say we have a `circle`

(where `dim = 2 ^ scale =`

`128`

is
the width and height of the following images):

```
pythagoras' :: Int -> Int -> Int
= a ^ 2 + b ^ 2 -- There's no need to take the square root
pythagoras' a b
circle :: Shape
= let centre = dim `div` 2
circle = pythagoras' (x - centre) (y - centre) < (centre ^ 2)
p [x, y] in Shape 2 (2 * centre) p
```

Here’s what we get when we use an axis-aligned curve to trace a
black-to-white gradient through the `circle`

:

```
= aaPixels circle
circlePixels
= let this = DM.lookup [x, y] circlePixels
drawCircle x y in maybe 255 id this
```

## Aside

Another thing we can do with `circle`

is to approximate pi:

`pi * r^2`

is the area of any circle`r = dim `div` 2`

in our example

`sRange s ^ sDim s`

is the area of the bounding box of`s :: Shape`

`sRange circle = dim = 2 * r`

`sDim circle = 2`

`boxArea = (2 * r)^2 = 4 * r^2`

for`circle`

`circleArea / boxArea = (pi * r^2) / (4 * r^2) = pi / 4`

follows from simple algebra- Therefore
`pi = 4 * circleArea / boxArea`

- Therefore
- Since each
`Point`

is an uniform distance from its neighbours, counting how many are in a`Shape`

is a measure of the`Shape`

’s area`aaArea = length . aaShape`

gives us the area inside a`Shape`

`circleArea = fromIntegral $ aaArea circle`

`boxArea = fromIntegral $ aaArea (Shape (sDim circle) (sRange circle) (const True))`

- Plugging these values into our definition of pi gives
`3.088516315125293`

- Increasing the radius decreases the error, since the sampling gives a less ‘jagged’ approximation of our circle

### An Unbounded Example

What happens if our `Range`

is
unbounded (ie. `range 0`

)?
For example, we might define an infinitely-repeating pattern:

```
checkerboard :: Shape
= let f = (`mod` 2) . (`div` 8)
checkerboard = f x == f y
g [x, y] in Shape 2 0 g
```

Obviously we can’t draw the whole pattern, but we can draw a small section:

`= sPred checkerboard [x, y] drawBoard x y `

Since the area of `checkerboard`

is infinite, so is the
length of a `Curve`

traced
through it. However, an infinite `Curve`

returned
by `aaCurve`

will *not* contain every `Point`

in the
`Shape`

.

This is because we only add a `Point`

from the
second row once we’ve reached the end of the first row; since the first
row never ends, we’ll never add a `Point`

from any
other row!

## Diagonal Traces

Cantor’s approach handles infinite patterns like `checkerboard`

by tracing
*diagonal* lines across the shape, from one coordinate axis to
another:

- Each
`Point`

on the`x`

axis is the start of a diagonal line - To get from one
`Point`

in a line to the next, we decrement the`x`

coordinate and increment the`y`

- If we have more dimensions, we fix the first coordinate (ie.
`x`

) and recurse using the rest of the dimensions

- If we have more dimensions, we fix the first coordinate (ie.
- Once the
`x`

coordinate hits`0`

, we jump to the start of the next line

```
= True
cantorMax [_] :xs) = sum xs == 0
cantorMax (x
1 = [n]
cantorStart n = 0 : cantorStart n (d-1)
cantorStart n d
cantorNext :: Point -> Point
:xs) | cantorMax (x:xs) = xs ++ [1+x]
cantorNext (x:xs) | cantorMax xs = (x + 1) : cantorStart (sum xs - 1) (length xs)
cantorNext (x:xs) | otherwise = x : cantorNext xs
cantorNext (x
-- A full curve
cantorCurve :: Range -> Dimensions -> Curve
= takeWhile ((<= 2 * r) . sum) (iterate cantorNext (replicate d 0))
cantorCurve r d
cantorShape :: Shape -> Curve
Shape d r p) = filter p (cantorCurve r d) cantorShape (
```

To see how this works, we can trace a black-to-white gradient across
a square, following the curve given by `cantorCurve`

. Compare it to the
axis-aligned version above:

We start in the top left corner and draw a *diagonal* line
from the top edge to the left edge, then draw another next to it, and
another next to it, and so on. Note that Cantor’s method naturally draws
a *triangle*; to make it trace a square, we’ve had to filter out
those points which extend too far to the right or the bottom.

### A Finite Example

Let’s revisit our `circle`

. If
we trace a gradient across it using Cantor’s method, we get the
following:

### Unbounded Example

If we apply this to the checkerboard pattern, we’re now guaranteed to reach any finite coordinate in finite time:

### Removing All Bounds

The checkerboard example is unbounded on the right and bottom, but
*does* have a bound on the top and the left. Cantor’s method can
exploit this to zig-zag across the pattern, but it doesn’t *rely*
on there being any bounds. Instead of zig-zagging, we can follow a
*spiral*, starting from any point, and be guaranteed to
eventually reach all points. For example, if we treat the checkerboard
as unbounded in *all* directions: