Sierpinski triangle (Erlang)
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, in Erlang.
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.
@
@@@
@@ @@
@@@@@@@
@@ @@
@@@@ @@@@
@@ @@ @@ @@
@@@@@@@@@@@@@@@
@@ @@
@@@@ @@@@
@@ @@ @@ @@
@@@@@@@@ @@@@@@@@
@@ @@ @@ @@
@@@@ @@@@ @@@@ @@@@
@@ @@ @@ @@ @@ @@ @@ @@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@ @@
@@@@ @@@@
@@ @@ @@ @@
@@@@@@@@ @@@@@@@@
@@ @@ @@ @@
@@@@ @@@@ @@@@ @@@@
@@ @@ @@ @@ @@ @@ @@ @@
@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@
@@ @@ @@ @@
@@@@ @@@@ @@@@ @@@@
@@ @@ @@ @@ @@ @@ @@ @@
@@@@@@@@ @@@@@@@@ @@@@@@@@ @@@@@@@@
@@ @@ @@ @@ @@ @@ @@ @@
@@@@ @@@@ @@@@ @@@@ @@@@ @@@@ @@@@ @@@@
@@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
Implementation
We internally represent the Empty and Full states as the erlang macros EMPTY and FULL. The state transformation rule is implemented using erlang's pattern matching, here presented in full:
<<directives>>= -module(sier). -compile(export_all). -define(FULL, $@). % the 'at' sign -define(EMPTY, $\s). % blank <<rules>>= rule([?EMPTY, ?EMPTY, ?EMPTY]) -> ?EMPTY; rule([?EMPTY, ?EMPTY, ?FULL]) -> ?FULL; rule([?EMPTY, ?FULL, ?EMPTY]) -> ?FULL; rule([?EMPTY, ?FULL, ?FULL]) -> ?FULL; rule([?FULL, ?EMPTY, ?EMPTY]) -> ?FULL; rule([?FULL, ?EMPTY, ?FULL]) -> ?FULL; rule([?FULL, ?FULL, ?EMPTY]) -> ?FULL; rule([?FULL, ?FULL, ?FULL]) -> ?EMPTY.
We represent the state of the cellular automaton in a given generation as a list of cell states of size AUTOMATA_SIZE. The initial automaton state is set to Empty, with the exception of the middle cell in the list, which is Full.
<<initial state>>= init_states(Width) -> Zeros = [?EMPTY || _ <- lists:seq(0, trunc(Width/2))], Zeros ++ [?FULL] ++ Zeros.
For each automaton we derive it's neighborhood. We assume that the states at either end of the automaton space have neighbors that are always empty:
<<compute neighborhood>>= neighborhood(L, 1, _) -> [?EMPTY] ++ lists:sublist(L, 2); neighborhood(L, N, Width) when N == Width -> lists:sublist(L, N - 1, 2) ++ [?EMPTY]; neighborhood(L, N, _) -> lists:sublist(L, N - 1, 3).
To run the automaton we provide a simple function that takes as an argument the number of generations to create, and prints successive generations to the screen. We use nested list comprehensions to compute the new state. The inner list comprehension gets a list of neigborhoods, then the outer list comprehension computes the new state of the cell by the application of the state rules.
<<sierpinski.erl>>= directives initial state rules compute neighborhood start() -> % main Width = 81, % needs to be an odd number to account for the middle starting point NGens = 40, State = init_states(Width), apply_rules(State, NGens, Width). apply_rules(_, 0, _) -> ok; apply_rules(State, Num, Width) -> io:format("~s~n", [State]), New_state = [rule(L) || L <- [neighborhood(State, N, Width) || N <- lists:seq(1, Width)]], apply_rules(New_state, Num - 1, Width).
| Download code |