Sierpinski triangle (Haskell)

From LiteratePrograms

Jump to: navigation, search
Other implementations: C | Erlang | Forth | Haskell | JavaScript | OCaml | Perl | Python | Scheme | Sed

The following is an implementation of the one-dimensional cellular automata and the Sierpinski cellular automaton in particular.

A one-dimensional cellular automaton is a linear space of cells, each of which has a state. The automaton changes in discrete time steps called generations. In each generation the state of each cell is decided according to a set of rules that is based on the states of neighboring cells. In the case of one-dimensional cellular automaton each cell has its state decided by considering three cells, itself and its left and right neighboring cells. Neighbouring the first and last cells of the space, we will assume virtual cells that are always in a default state.

The Sierpinski cellular automaton has two states, Empty and Full. The only rule states that a cell will be set to Full if and only if of the three states considered exactly one or two are Full.

When run output similar to the following will be produced. 

                               @
                              @@@
                             @@ @@
                            @@@@@@@
                           @@     @@
                          @@@@   @@@@
                         @@  @@ @@  @@
                        @@@@@@@@@@@@@@@
                       @@             @@
                      @@@@           @@@@
                     @@  @@         @@  @@
                    @@@@@@@@       @@@@@@@@
                   @@      @@     @@      @@
                  @@@@    @@@@   @@@@    @@@@
                 @@  @@  @@  @@ @@  @@  @@  @@
                @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
               @@                             @@
              @@@@                           @@@@
             @@  @@                         @@  @@
            @@@@@@@@                       @@@@@@@@
           @@      @@                     @@      @@
          @@@@    @@@@                   @@@@    @@@@
         @@  @@  @@  @@                 @@  @@  @@  @@
        @@@@@@@@@@@@@@@@               @@@@@@@@@@@@@@@@
       @@              @@             @@              @@
      @@@@            @@@@           @@@@            @@@@
     @@  @@          @@  @@         @@  @@          @@  @@
    @@@@@@@@        @@@@@@@@       @@@@@@@@        @@@@@@@@
   @@      @@      @@      @@     @@      @@      @@      @@
  @@@@    @@@@    @@@@    @@@@   @@@@    @@@@    @@@@    @@@@
 @@  @@  @@  @@  @@  @@  @@  @@ @@  @@  @@  @@  @@  @@  @@  @@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@

Let us begin by defining a Haskell module. 

<<Cellular.hs>>=
module Cellular where
Cellular

For our purposes we will only consider one rule. A cellular automaton consists of a Rule and a default value from a set of states. 

<<Cellular>>=
type Cellular a = (Rule a, a)

It is simple to create an enumerated type for the Empty and Full states of the Sierpinski automaton. 

<<Cellular>>=
data EmptyFull = E | F 
instance Show EmptyFull where
    show E = " "
    show F = "@"


Our state space will be a regular Haskell list. It will be easy to add new state sets because the element type of the list is polymorphic. We will represent a rule as a function that takes the states of three neigbouring cells and returns the new state of the center cell. 


<<Cellular>>=
type Space a = [a]
type Rule a = a -> a -> a -> a

A state space is created for the initial generaton of the Sierpinski automaton. 

<<Cellular>>=
space :: Space EmptyFull
space = blanks ++ [F] ++ blanks
        where 
            blanks = replicate 32 E

The Rule of the Sierpinski automaton is that a cell will be full in the next generation if exactly one or two of the tested cells are full. 

<<Cellular>>=
rule :: Rule EmptyFull
rule F E E = F
rule E F E = F
rule E E F = F
rule E F F = F
rule F E F = F
rule F F E = F
rule _ _ _ = E

Now we will define the Sierpinski cellular automaton as the above rule with the default value of E for empty. 

<<Cellular>>=
sier :: Cellular EmptyFull
sier = (rule, E)

The nextGen function takes an automaton and a state space and generates the next generation. If applied to an empty space [] it will return []. The virtual cells are added to both ends of the space and then the next generation is created by successivly applying the Rule. 

<<Cellular>>=
nextGen :: Cellular a -> Space a -> Space a
nextGen (rule,def) s   = nextGenAux (def : s ++ [def])
    where
        nextGenAux (a:b:c:xs) = rule a b c : nextGenAux (b:c:xs)
        nextGenAux _          = []

The generateSierpinski function generates a list of spaces that represents a run of the automaton. This function will diverge if applied to a non-positive argument. 

<<Cellular>>=
generateSierpinski :: Integer -> [[EmptyFull]]
generateSierpinski = aux space
                     where aux s 1 = [s]
                           aux s n = s : aux (nextGen sier s) (n-1)

The runSierpinski function is an IO action that prints a representation of the run to the console. 

<<Cellular>>=
runSierpinski :: Integer -> IO ()
runSierpinski n = if n <= 0 then error "please supply a positive integer" else
                  aux (generateSierpinski n)
                  where aux []     = do putStr "\n"
                                        return ()
                        aux (x:xs) = do putStr $ "\n" ++ concatMap show x
                                        aux xs

ToDo List

This program could be extended in many ways:

  • Add a new rule and state space.
  • Make the program more general, capable of running several different rules.
  • The rule function can be rewritten to be several lines shorter.
  • Add to the explanations.
  • Add the capability of dynamically changing the characters that are output.

Everyone is invited to upgrade this program. Lets make some good code.

Download code
Retrieved from "http://literateprograms.org/Sierpinski_triangle_%28Haskell%29"
Views