Programming Praxis – Cellular Automata

Today’s Programming Praxis problem is about cellular automata. Let’s dive in.

As usual, our imports:

import Data.Bits
import Data.List

Programming Praxis’ author uses ones and zeros to represent on and off cells. That works, but you run the risk of accidentally having another number somewhere and crashing your program. We Haskell programmers like our type safety, so we’re going to use booleans. First we need a function to get the successor of a group of cells:

successor :: Int -> [Bool] -> Bool
successor r bs = testBit r . sum $
                 zipWith (shiftL . fromEnum) (reverse bs) [0..]

Using that, we can generate the next row as follows:

nextRow :: Int -> [Bool] -> [Bool]
nextRow r xs = map (successor r) . take (length xs) . transpose .
               take 3 . iterate (drop 1) $ [head xs] ++ xs ++ [last xs]

Since lists of booleans are not that easy to read, let’s use spaces and Xs.

displayRow :: [Bool] -> String
displayRow = intersperse ' ' . map (\b -> if b then 'X' else ' ')

Each run starts with one active cell and simply consists of repeating nextRow as often as needed.

cells :: Int -> Int -> [String]
cells r h = map displayRow . take (h + 1) . iterate (nextRow r) $
            replicate h False ++ [True] ++ replicate h False

And finally we test out program. Let’s make a lovely Sierpinski triangle:

main :: IO ()
main = mapM_ putStrLn $ cells 82 15

Done. 10 lines of code. Not bad.

About these ads

Tags: , , , , ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Follow

Get every new post delivered to your Inbox.

Join 35 other followers

%d bloggers like this: