The little Haskell toy I wrote to simulate a dot-matrix printhead was useful in one sense: it helped me learn a little more Haskell! I couldn't help noticing that the results look like the transformations you get when applying simple cellular automata rules. So my next experiment is to implement those rules, and see what else I can learn from the results.
What follows is Literate Haskell, but there is no main program to run; it is for you to experiment with interactively, if you like.
Some Haskell code to implement simple cellular automata (CA) rules: part one, round one. The simplest type of one-dimensional CA behaves as follows: - a cell may be on or off (one or zero). - time ticks by in discrete intervals. - at each tick, the state of each cell is updated using a function that maps the current state of the cell to the left, the cell itself, and the cell to the right to the new cell value. Because this value-generating function depends on 3 bits of input, a given CA rule actually consists of 2^3 = 8 possible mappings. The mappings can be represented by the binary values 0b000 to 0b111 (decimal 0..7). By Wolfram's numbering convention for these simple CA, we actually count down from 7 to 0. So, let's say we have a rule that maps each possible set of left, center, and right values: 0b111, 0b110, 0b101, 0b100, 0b011, 0b010, 0b001, 0b000 to the new cell value: 0b0, 0b0, 0b0, 0b1, 0b1, 0b1, 0b1, 0b0 We can treat the resulting number, in this case 0b00011110, as the rule number. This is rule 30 in Wolfram's schema; there are 2^8, or 256, possible rules, numbered from 0 to 255. First, let's make a function that, given a rule number and three values (left, center, and right), returns the new cell state. We turn the three values into an index to look up the appropriate bit in the rule number. >import Data.Bits >genNextBit :: Int -> ( Bool, Bool, Bool ) -> Bool >genNextBit rulenum ( left, center, right ) = rulenum `testBit` idx > where idx = ( if left then (4::Int) else (0::Int) ) .|. > ( if center then (2::Int) else (0::Int) ) .|. > ( if right then (1::Int) else (0::Int) ) Hmmm... it is lacking a certain elegance, and I don't quite like the way the indentation rules work in this case, but let's test it with a function that generates the 8 rule indices in the form of tuples: >genRuleIndices :: [( Bool, Bool, Bool )] >genRuleIndices = [ ( (val `testBit` 2), (val `testBit` 1), > ( val `testBit` 0) ) | val <- [(7::Int), > (6::Int)..(0::Int)] ] Now if we write: genRuleIndices we get: [(True,True,True), (True,True,False), ... (False,False,True), (False,False,False)] and if we write: map (genNextBit 30) genRuleIndices this expression curries us a function (mmm... curry!) which takes a starting state and applies rule 30, then feeds it the possible starting states. The result is: [False,False,False,True,True,True,True,False] That looks like the bit pattern for rule 30. Just for fun, let's confirm by making a function that will translate a list of output bit values back into a rule number. The signature should look like this: sumBitVals :: [Bool] -> Int And we want the list >test_bit_vals = [False,False,False,True,True,True,True,False] to map back to 30. Take a shot at it yourself; you might find that the result is instructional I'll wait. (Musical interlude). Did you try it? Let's look at some possible implementation strategies. We could make a list of the powers of two and then do some list manipulation to get the powers of two that correspond to our one-bits summed up: >powers_of_two_8_bits = reverse ( take 8 (iterate (2 *) 1) ) [128,64,32,16,8,4,2,1] (An aside: since this is generated by a function that takes no parameters at runtime, it would seem like a sufficiently smart compiler could generate this list and stick it in the resulting program so that no run-time calculation is required to generate it. Does GHC do this? I don't know.) Anyway, our implementation. We can tuple up our powers of two with our bit values: >tups = zip powers_of_two_8_bits test_bit_vals [(128,False),(64,False),(32,False),(16,True),(8,True),(4,True),(2,True),(1,False)] Then we can turn this back into a list of only the powers of two that are "on," and sum the results: sum (map (\ tup -> if snd tup then fst tup else 0) tups ) 30 It seems like this should be simpler still. I looked in the standard library for a function to filter one list using a list of boolean values as a comb. Let's write one: >combListWithList :: [a] -> [Bool] -> [a] >combListWithList   =  >combListWithList ls comb = > if (head comb) then (head ls) : combListWithList (tail ls) (tail comb) > else combListWithList (tail ls) (tail comb) combListWithList powers_of_two_8_bits test_bit_vals [16,8,4,2] That seems good, although it doesn't express the idea that the lists have to be the same length. It still seems amazing to me that I can reel off functions like that in Haskell and have them work right the first time! Now we can produce our final function: >sumBitVals :: [Bool] -> Int >sumBitVals ls = sum $ combListWithList powers_of_two_8_bits ls sumBitVals test_bit_vals 30 There is probably an elementary way to implement the above function using zipWith instead of my combList, but I'll leave that to you; leave a comment if you figure it out! As another aside, here is another function I came up with to generate this bit vals; it doesn't rely on a specific length. >foldBitVals :: [Bool] -> Int >foldBitVals ls = snd (foldr > (\ flag tup -> if flag then ((fst tup) * 2, (snd tup) + (fst tup)) > else ((fst tup) * 2, snd tup) ) > (1, 0) ls ) foldBitVals test_bit_vals 30 Take a moment to understand the above function; it is a little strange. I perform a fold using a tuple. The first element is the power of two, so it keeps track of our place in the list, and the second is an accumulator as we add up our values. This is a trick for stashing a state that is more complex than a single value into a fold.
Anyway, that was a long diversion, so let's end for now. Next time we'll look at ways to represent our CA universe as it evolves by applying our rules. As always, your comments are welcome!