L-System

lsystem.hs

import Control.Monad

data LSymbol = LRule Char | LDeriv String

type Alphabet = [LSymbol]

type Axiom = [LSymbol]

-- a production is a finite mapping of LSymbol -> LSymbol
-- if no production exists for a given LSymbol on the LHS of a Production
-- then an idempotent production is assumed, that is, identity
data Production = Production LSymbol LSymbol deriving (Show)

type Productions = [Production]

instance Eq LSymbol where
    (LRule a) == (LDeriv b) = [a] == b

instance Show LSymbol where
    show (LRule a) = [a]
    show (LDeriv a) = a

instance Eq Production where
    (Production a b) == (Production a' b') = a == a' && b == b'

tryProd [] symb = symb
tryProd ((Production pred succ):ps) symb
    | pred == symb = succ
    | otherwise = tryProd ps symb

prodToDeriv xs = convert (map (tryProd prods) xs) where
    convert ((LDeriv derivation):[]) = map (LDeriv . (:[])) derivation
    convert ((LDeriv derivation):ds) = (map (LDeriv . (:[])) derivation) ++ (convert ds)

prods = [Production (LRule 'A') (LDeriv "AB"), Production (LRule 'B') (LDeriv "A"), Production (LRule 'C') (LDeriv "CBCA")]
axioms = [LDeriv "ACBC"]

main = print $ join $ map show $ foldr (\_ a -> prodToDeriv a) axioms [1..14]