# 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
aaCurve r 1 = [[x] | x <- range r]
aaCurve r n = [x:xs | x <- range r, xs <- aaCurve r (n - 1)]
aaShape :: Shape -> Curve
aaShape (Shape d r p) = filter p (aaCurve r d)
```

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

:

```
circlePixels = aaPixels circle
drawCircle x y = let this = DM.lookup [x, y] circlePixels
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
checkerboard = let f = (`mod` 2) . (`div` 8)
g [x, y] = f x == f y
in Shape 2 0 g
```

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

`drawBoard x y = sPred checkerboard [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

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

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: