Towards the Cantor set

Today we will “construct” the standard (ternary) Cantor set [1]. We start with the closed unit interval , and then remove its open middle third to obtain . We then remove the open middle thirds of each of these two intervals to obtain

and, continuing this process ad infinitum, we obtain a nested sequence of compact sets . Note that is the union of intervals, each of length . We refer to the following set

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 can be represented by an ordered pair . Each set can be represented by a list of ordered pairs, where each pair represents a closed interval. We create a function that takes and returns . 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

Tags: Cantor Set, Data.Ratio, Haskell