# Rod Carvalho

## Towards the Cantor set

Today we will “construct” the standard (ternary) Cantor set [1]. We start with the closed unit interval $\mathcal{C}_0 := [0,1]$, and then remove its open middle third $]1/3, 2/3[$ to obtain $\mathcal{C}_1 := [0, 1/3] \cup [2/3, 1]$. We then remove the open middle thirds of each of these two intervals to obtain

$\mathcal{C}_2 := [0, 1/9] \cup [2/9, 3/9] \cup [6/9, 7/9] \cup [8/9, 1]$

and, continuing this process ad infinitum, we obtain a nested sequence of compact sets $\mathcal{C}_0 \supset \mathcal{C}_1 \supset \mathcal{C}_2 \supset \dots$. Note that $\mathcal{C}_n$ is the union of $2^n$ intervals, each of length $3^{-n}$. We refer to the following set

$\mathcal{C} := \displaystyle\bigcap_{n=0}^{\infty} \mathcal{C}_n$

as the standard (ternary) Cantor set. This set is most interesting, indeed, since it is uncountable and has Lebesgue measure zero [1].

__________

In Haskell

In Haskell, a closed interval $[a, b]$ can be represented by an ordered pair $(a,b)$. Each set $\mathcal{C}_n$ can be represented by a list of ordered pairs, where each pair represents a closed interval. We create a function $f$ that takes $\mathcal{C}_n$ and returns $\mathcal{C}_{n+1} = f ( \mathcal{C}_n )$. We will work with arbitrary-precision rational numbers, not floating-point numbers.

The following Haskell script lazily generates the sequence of sets:

```import Data.Ratio

type Interval = (Rational, Rational)

-- remove the middle third of an interval
removeMiddleThird :: Interval -> [Interval]
removeMiddleThird (a,b) = [(a,b'),(a',b)] 
                     	  where b' = (2%3)*a + (1%3)*b
                                a' = (1%3)*a + (2%3)*b

-- define function f
f :: [Interval] -> [Interval]
f intervals = concat $ map removeMiddleThird intervals

-- create list of sets
sets :: [[Interval]]
sets = iterate f [(0,1)]

-- define Lebesgue measure
measure :: Interval -> Rational
measure (a,b) = b - a```

Note that we used function iterate to generate the sequence of sets. Here is a GHCi session:

```*Main> -- take first 4 sets
*Main> take 4 sets
[[(0 % 1,1 % 1)],[(0 % 1,1 % 3),(2 % 3,1 % 1)],
[(0 % 1,1 % 9),(2 % 9,1 % 3),(2 % 3,7 % 9),(8 % 9,1 % 1)],
[(0 % 1,1 % 27),(2 % 27,1 % 9),(2 % 9,7 % 27),(8 % 27,1 % 3),
(2 % 3,19 % 27),(20 % 27,7 % 9),(8 % 9,25 % 27),(26 % 27,1 % 1)]]
*Main> -- compute measure of C_0
*Main> sum $ map measure (sets !! 0) 
1 % 1
*Main> -- compute measure of C_1
*Main> sum $ map measure (sets !! 1) 
2 % 3
*Main> -- compute measure of C_2
*Main> sum $ map measure (sets !! 2) 
4 % 9
*Main> -- compute measure of C_3
*Main> sum $ map measure (sets !! 3) 
8 % 27```

This is arguably the most useless Haskell script ever written.

__________

References

[1] Charles Chapman Pugh, Real Mathematical Analysis, Springer-Verlag, New York, 2002.

About these ads

### Like this:

Like Loading...

Tags: Cantor Set, Data.Ratio, Haskell

This entry was posted on August 3, 2012 at 10:30 and is filed under Haskell, Mathematics. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

%d bloggers like this:
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 15, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": false}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.8733580708503723, "perplexity_flag": "head"}