Formalisation of Cellular Automaton & running rule 90

Cellular.hs

module Data.Cellular where

import Data.Monoid
import Data.Function.Memoize

newtype Cellular g a = Cellular { delta :: (g -> a) -> a }

step :: Monoid g => Cellular g a -> (g -> a) -> (g -> a)
step (Cellular d) init g = d (init . (g <>))

run :: (Monoid g, Memoizable g) => Cellular g a -> (g -> a) -> [g -> a]
run = iterate . (memoize .) . step

Main.hs

module Main where

import Data.Cellular
import Data.Bits
import Data.List
import Data.Monoid
import Control.Monad

rule90 :: Cellular Integer Bool
rule90 = Cellular $ \ state -> state (-1) `xor` state 1

instance Monoid Integer where
  mempty      = getSum mempty
  mappend m n = getSum $ Sum m `mappend` Sum n

display :: (Integer -> Bool) -> Integer -> Integer -> String
display state m n = fmap (toChar . state) [m..n]
  where toChar b = if b then 'X' else ' '

initAutomata :: String -> (Integer -> Bool)
initAutomata st =
  let width = genericLength st - 1 in
  \ n -> if n < 0 || width < n
         then False
         else (1 ==) $ read $ (:[]) $ genericIndex st n

main :: IO ()
main = do
  st <- getLine
  ns <- getLine
  let width = genericLength st - 1
  let trace = take (read ns) $ run rule90 $ initAutomata st
  forM_ trace $ \ tr -> putStrLn $ display tr 0 width