purely functional turing machine simulator

turing-sim..hs

module Main where

data Stream a = Stream a (Stream a) deriving (Eq, Show, Functor)
data Zipper a = Zipper { zl :: (Stream a)
                       , ze :: a 
                       , zr :: (Stream a)
                       } deriving (Eq, Show, Functor)

srepeat :: a -> Stream a
srepeat a = go where go = Stream a go

sfromList :: [a] -> Stream (Maybe a)
sfromList = foldr Stream (srepeat Nothing) . map Just

zfromList :: [a] -> Zipper (Maybe a)
zfromList as = Zipper (srepeat Nothing) a r where
  Stream a r = sfromList as

write :: a -> Zipper a -> Zipper a
write a (Zipper l _ r) = Zipper l a r

data Dir = L | R deriving (Eq, Show)

move :: Dir -> Zipper a -> Zipper a
move L (Zipper (Stream a' l) a r) = Zipper l a' (Stream a r)
move R (Zipper l a (Stream a' r)) = Zipper (Stream a l) a' r

type Delta q a = q -> a -> (q, a, Dir)

data Desc q a = Desc q (Zipper a)

step :: Delta q a -> Desc q a -> Desc q a
step delta (Desc q z) = 
  let (q', a', d) = delta q $ ze z
   in Desc q' $ move d $ write a' z

run :: Delta q a -> Desc q a -> [Desc q a]
run = iterate . step