Sierpinski triangle (OCaml)
From LiteratePrograms
- 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 an OCaml file.
<<cellular.ml>>= Cellular
It is simple to create an enumerated type for the Empty and Full states of the Sierpinski automaton.
<<Cellular>>= type empty_full = E | F let char_of_ef = function E -> ' ' | F -> '@'
Our state space will be a regular OCaml 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 'a space = 'a list type 'a rule = ('a * 'a * 'a) -> 'a
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 'a cellular = 'a rule * 'a
A state space is created for the initial generaton of the Sierpinski automaton.
<<Cellular>>= let space : empty_full space = let blanks = Array.to_list (Array.make 32 E) in blanks @ F :: blanks
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>>= let rule : empty_full rule = function F,E,E | E,F,E | E,E,F | E,F,F | F,E,F | F,F,E -> F | _ -> E
Now we will define the Sierpinski cellular automaton as the above rule with the default value of E for empty.
<<Cellular>>= let sier : empty_full cellular = rule, E
The next_gen 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 successively applying the rule.
<<Cellular>>= let next_gen (rule,def:'a cellular) (s:'a space) : 'a space = let rec next_gen_aux = function a::b::c::xs -> rule (a, b, c) :: next_gen_aux (b::c::xs) | _ -> [] in next_gen_aux (def :: s @ [def])
The run_sierpinski function prints each of the spaces in a run of the automaton to the console.
<<Cellular>>= let run_sierpinski (n:int) : unit = let s = ref space in for i = 1 to n do List.iter print_char (List.map char_of_ef !s); print_newline (); s := next_gen sier !s done
We might call it like this:
# run_sierpinski 32;;
@
@@@
@@ @@
@@@@@@@
@@ @@
@@@@ @@@@
@@ @@ @@ @@
@@@@@@@@@@@@@@@
@@ @@
@@@@ @@@@
@@ @@ @@ @@
@@@@@@@@ @@@@@@@@
@@ @@ @@ @@
@@@@ @@@@ @@@@ @@@@
@@ @@ @@ @@ @@ @@ @@ @@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@ @@
@@@@ @@@@
@@ @@ @@ @@
@@@@@@@@ @@@@@@@@
@@ @@ @@ @@
@@@@ @@@@ @@@@ @@@@
@@ @@ @@ @@ @@ @@ @@ @@
@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@
@@ @@ @@ @@
@@@@ @@@@ @@@@ @@@@
@@ @@ @@ @@ @@ @@ @@ @@
@@@@@@@@ @@@@@@@@ @@@@@@@@ @@@@@@@@
@@ @@ @@ @@ @@ @@ @@ @@
@@@@ @@@@ @@@@ @@@@ @@@@ @@@@ @@@@ @@@@
@@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
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 |