#### rule110.lhs:

This Haskell file implements Rule 100. Rule 110 is a cellular automaton rule

for a 1D cellular automaton.

The state of the cellular automaton is a string that is infinite in both

directions and contains 0s and 1s. Updating the state of the string consists

of replacing each value with a new value based on its context. Patterns

"111", "100", and "000" result in the value "0" at the center, and all other

patterns result in the value "1" at their center.

We can't update an arbitrary infinite string in finite time, but the kinds of

strings we work with are zero except for a finite substring in the middle.

Let's start with a replacement rule that isn't quite right but gets most

of the job done.

> repl110 :: String -> String

> repl110 s | (length s < 3) = s

> repl110 s | take 3 s `elem` ["111","100","000"] = '0' : repl110 (tail s)

> repl110 s = '1' : repl110 (tail s)

That rule isn't quite right because it doesn't do the right thing at the ends

of the string. We could write special case code for that, but that's a lot of work.

It's easier just to stick some zeros on both ends, perform the substitutions, and

then delete whatever is left.

> rule110 :: String -> String

> rule110 s = trim0s (repl110 ("000" ++ s ++ "000"))

To make this work, we need to write a function that trims the 0s off both ends

of the string. First, let's write a function that trims 0s off the left end.

> drop0s :: String -> String

> drop0s ('0':s) = drop0s s

> drop0s s = s

To trim 0s off both ends, we just trim, reverse, trim again, and reverse again.

This is a common trick (albeit a bit inefficient).

> trim0s :: String -> String

> trim0s s = reverse (drop0s (reverse (drop0s s)))

There is a function called "iterate f start" in Haskell that generates an infinite list

obtained by applying the same function f again and again, first to the start value, then

to the result of that, etc. With that, we can now easily look at what happens after many

applications of Rule 110:

> main = print ((iterate rule110 "1") !! 1000)