Sierpinski Carpet
The Sierpiński carpet is a plane fractal first described by Wacław Sierpiński in 1916. Your task is to generate this fractal in a text format represented as a list of strings. Each string represents a single row in the picture. The picture is defined recursively. For , we define . For , we define as shown below.
In other words, consists of eight copies of and the middle box of the same size as filled with spaces. The first iterations , , , and look as follows:
# ### ######### ###########################
# # # ## ## # # ## ## ## ## ## ## ## ## #
### ######### ###########################
### ### ### ###### ###### ###
# # # # # # # ## # # ## # # #
### ### ### ###### ###### ###
######### ###########################
# ## ## # # ## ## ## ## ## ## ## ## #
######### ###########################
######### #########
# ## ## # # ## ## #
######### #########
### ### ### ###
# # # # # # # #
### ### ### ###
######### #########
# ## ## # # ## ## #
######### #########
###########################
# ## ## ## ## ## ## ## ## #
###########################
### ###### ###### ###
# # # ## # # ## # # #
### ###### ###### ###
###########################
# ## ## ## ## ## ## ## ## #
###########################The size of the picture grows exponentially with .
IO Program
In Haskell, implement a function of type Int -> [String] that for a given natural number returns the Sierpiński carpet represented as a list of strings. Further, create an IO program allowing the user to enter the number . As the size of the carpet quickly grows, it also asks the user to enter a window to be displayed. More precisely, the user enters four numbers row1, row2, col1, and col2 separated by spaces. The program then displays the part of the carpet starting on the row row1 and the column col1, and ending on the row row2-1 and the column col2-1. The rows and columns are indexed from . You may assume only valid inputs.
Examples
Enter n:
2
Enter row1 row2 col1 col2:
0 4 0 8
########
# ## ##
########
### ##Enter n:
4
Enter row1 row2 col1 col2:
10 11 18 36
# ## ## ## ## ## #Make sure your program outputs the messages as in the examples (i.e. Enter n:, etc). Otherwise the automatic evaluation will fail.
Your file has to be called Sierpinsky.hs.
Hints
To join the boxes represented as lists of strings in the top figure you may find the function
zipWith3 :: (a -> b -> c -> d) -> [a] -> [b] -> [c] -> [d]usefule, which, for a ternary function and three lists , , creates a list of values .
To generate lists of a repeated value, you can use the function:
replicate :: Int -> a -> [a]To truncate a list e.g. from st to end use the following function:
cut :: Int -> Int -> [a] -> [a]
cut st end = take (end-st) . drop stSolution
empty :: Int -> [String]
empty n = replicate n $ replicate n ' '
generateFractal :: Int -> [String]
generateFractal 0 = ["#"]
generateFractal n = upper ++ middle ++ upper
where fr = generateFractal (n-1)
size = length fr
upper = zipWith3 (\x y z -> x ++ y ++ z) fr fr fr
middle = zipWith3 (\x y z -> x ++ y ++ z) fr (empty size) fr
cut :: Int -> Int -> [a] -> [a]
cut st end = take (end-st) . drop st
main :: IO ()
main = do putStrLn "Enter n:"
n <- read <$> getLine
let fr = generateFractal n
putStrLn "Enter row1 row2 col1 col2:"
[r1,r2,c1,c2] <- map read . words <$> getLine
mapM_ (putStrLn . cut c1 c2) $ cut r1 r2 fr