An Odd Rewriting System/Odd.hs

This is an implementation, written in Haskell by Chris Pressey, of An Odd Rewriting System. It is only a partial implementation, because it doesn't implement parsing or the halting symbol.

import Data.Char

data Defn = Defn {
    symbol :: Char,
    oddDefn :: String,
    evenDefn :: String
} deriving (Show)

data Program = Program {
    defns :: [Defn],
    initial :: String
} deriving (Show)

isOdd = isUpper
isEven = isLower

findDefn char defnGetter [] = error "No such defn"
findDefn char defnGetter (defn:defns) =
    if symbol defn == char then defnGetter defn else findDefn char defnGetter defns

run program = evolve (initial program) (defns program)

evolve dataString defns =
    let
        dataString' = step dataString defns
    in
        [dataString] ++ evolve dataString' defns

step dataString defns =
   let
       (transformedSymbols, _) = foldl (transformSymbol) ([],0) dataString
   in
       concat transformedSymbols
   where
       transformSymbol (newElems, numSeenOddSymbols) char =
           let
               defnGetter = if numSeenOddSymbols `mod` 2 == 0 then evenDefn else oddDefn
               replacement = findDefn char defnGetter defns
               numSeenOddSymbols' = numSeenOddSymbols + if isOdd char then 1 else 0
           in
               (newElems ++ [replacement], numSeenOddSymbols')

To show that this implements the semantics of An Odd Rewriting System you can write something like

testProg1 = Program{
    initial = "Cwg",
    defns = [
        Defn{ symbol='c', evenDefn="c", oddDefn="C" },
        Defn{ symbol='C', evenDefn="C", oddDefn="c" },
        Defn{ symbol='g', evenDefn="wg",oddDefn="wg" },
        Defn{ symbol='w', evenDefn="w", oddDefn="C" }
    ]
}

test1 = take 20 (run testProg1)