{-# LANGUAGE FlexibleInstances #-}

-- |This module represents types of S-machine.
module SMType where

import Data.String
import Data.Set (Set)
import Prelude hiding (Word)
import TMType (TapeCommand, Square)

-- |This is state name data type of 'State'.
--
-- Every constructor here represents name of the 'State'.
data StateName = E | X | F | P | Q | R | S | T | U
   deriving (StateName -> StateName -> Bool
(StateName -> StateName -> Bool)
-> (StateName -> StateName -> Bool) -> Eq StateName
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: StateName -> StateName -> Bool
$c/= :: StateName -> StateName -> Bool
== :: StateName -> StateName -> Bool
$c== :: StateName -> StateName -> Bool
Eq, Eq StateName
Eq StateName
-> (StateName -> StateName -> Ordering)
-> (StateName -> StateName -> Bool)
-> (StateName -> StateName -> Bool)
-> (StateName -> StateName -> Bool)
-> (StateName -> StateName -> Bool)
-> (StateName -> StateName -> StateName)
-> (StateName -> StateName -> StateName)
-> Ord StateName
StateName -> StateName -> Bool
StateName -> StateName -> Ordering
StateName -> StateName -> StateName
forall a.
Eq a
-> (a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
min :: StateName -> StateName -> StateName
$cmin :: StateName -> StateName -> StateName
max :: StateName -> StateName -> StateName
$cmax :: StateName -> StateName -> StateName
>= :: StateName -> StateName -> Bool
$c>= :: StateName -> StateName -> Bool
> :: StateName -> StateName -> Bool
$c> :: StateName -> StateName -> Bool
<= :: StateName -> StateName -> Bool
$c<= :: StateName -> StateName -> Bool
< :: StateName -> StateName -> Bool
$c< :: StateName -> StateName -> Bool
compare :: StateName -> StateName -> Ordering
$ccompare :: StateName -> StateName -> Ordering
$cp1Ord :: Eq StateName
Ord)

instance Show StateName where
   show :: StateName -> String
show StateName
st =
      case StateName
st of
         StateName
E -> String
"E"
         StateName
X -> String
"x"
         StateName
F -> String
"F"
         StateName
P -> String
"p"
         StateName
Q -> String
"q"
         StateName
R -> String
"r"
         StateName
S -> String
"s"
         StateName
T -> String
"t"
         StateName
U -> String
"u"

-- |This is tag data type of 'State'.
--
-- 'Hat' it's like a house roof.
--
-- 'Quote' is a '.
--
-- 'Dash' is a overline.
data Tag = Hat | Quote | Dash
   deriving (Tag -> Tag -> Bool
(Tag -> Tag -> Bool) -> (Tag -> Tag -> Bool) -> Eq Tag
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: Tag -> Tag -> Bool
$c/= :: Tag -> Tag -> Bool
== :: Tag -> Tag -> Bool
$c== :: Tag -> Tag -> Bool
Eq, Eq Tag
Eq Tag
-> (Tag -> Tag -> Ordering)
-> (Tag -> Tag -> Bool)
-> (Tag -> Tag -> Bool)
-> (Tag -> Tag -> Bool)
-> (Tag -> Tag -> Bool)
-> (Tag -> Tag -> Tag)
-> (Tag -> Tag -> Tag)
-> Ord Tag
Tag -> Tag -> Bool
Tag -> Tag -> Ordering
Tag -> Tag -> Tag
forall a.
Eq a
-> (a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
min :: Tag -> Tag -> Tag
$cmin :: Tag -> Tag -> Tag
max :: Tag -> Tag -> Tag
$cmax :: Tag -> Tag -> Tag
>= :: Tag -> Tag -> Bool
$c>= :: Tag -> Tag -> Bool
> :: Tag -> Tag -> Bool
$c> :: Tag -> Tag -> Bool
<= :: Tag -> Tag -> Bool
$c<= :: Tag -> Tag -> Bool
< :: Tag -> Tag -> Bool
$c< :: Tag -> Tag -> Bool
compare :: Tag -> Tag -> Ordering
$ccompare :: Tag -> Tag -> Ordering
$cp1Ord :: Eq Tag
Ord, Int -> Tag -> ShowS
[Tag] -> ShowS
Tag -> String
(Int -> Tag -> ShowS)
-> (Tag -> String) -> ([Tag] -> ShowS) -> Show Tag
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [Tag] -> ShowS
$cshowList :: [Tag] -> ShowS
show :: Tag -> String
$cshow :: Tag -> String
showsPrec :: Int -> Tag -> ShowS
$cshowsPrec :: Int -> Tag -> ShowS
Show)

-- |'SMTag' is a tag for S-machines and shows what kind is it.
--
-- 'T4' for S-machine number 4.
--
-- 'T9' for number 9.
--
-- 'TAlpha' for alpha S-machine.
--
-- 'TOmega' for omega S-machine.
data SMTag = T4 | T9 | TAlpha | TOmega
   deriving (SMTag -> SMTag -> Bool
(SMTag -> SMTag -> Bool) -> (SMTag -> SMTag -> Bool) -> Eq SMTag
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: SMTag -> SMTag -> Bool
$c/= :: SMTag -> SMTag -> Bool
== :: SMTag -> SMTag -> Bool
$c== :: SMTag -> SMTag -> Bool
Eq, Eq SMTag
Eq SMTag
-> (SMTag -> SMTag -> Ordering)
-> (SMTag -> SMTag -> Bool)
-> (SMTag -> SMTag -> Bool)
-> (SMTag -> SMTag -> Bool)
-> (SMTag -> SMTag -> Bool)
-> (SMTag -> SMTag -> SMTag)
-> (SMTag -> SMTag -> SMTag)
-> Ord SMTag
SMTag -> SMTag -> Bool
SMTag -> SMTag -> Ordering
SMTag -> SMTag -> SMTag
forall a.
Eq a
-> (a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
min :: SMTag -> SMTag -> SMTag
$cmin :: SMTag -> SMTag -> SMTag
max :: SMTag -> SMTag -> SMTag
$cmax :: SMTag -> SMTag -> SMTag
>= :: SMTag -> SMTag -> Bool
$c>= :: SMTag -> SMTag -> Bool
> :: SMTag -> SMTag -> Bool
$c> :: SMTag -> SMTag -> Bool
<= :: SMTag -> SMTag -> Bool
$c<= :: SMTag -> SMTag -> Bool
< :: SMTag -> SMTag -> Bool
$c< :: SMTag -> SMTag -> Bool
compare :: SMTag -> SMTag -> Ordering
$ccompare :: SMTag -> SMTag -> Ordering
$cp1Ord :: Eq SMTag
Ord)

instance Show SMTag where
   show :: SMTag -> String
show SMTag
tag =
      case SMTag
tag of
         SMTag
T4 -> String
"T_{4}"
         SMTag
T9 -> String
"T_{9}"
         SMTag
TAlpha -> String
"T_{\\alpha}"
         SMTag
TOmega -> String
"T_{\\omega}"

-- |This is data type of Turing machine commands and has uses in 'StateVal' in order to define for which command belongs to 'StatevVal'.
data TMCMD = Command [TapeCommand] | CommandAlias String
   deriving (Int -> TMCMD -> ShowS
[TMCMD] -> ShowS
TMCMD -> String
(Int -> TMCMD -> ShowS)
-> (TMCMD -> String) -> ([TMCMD] -> ShowS) -> Show TMCMD
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [TMCMD] -> ShowS
$cshowList :: [TMCMD] -> ShowS
show :: TMCMD -> String
$cshow :: TMCMD -> String
showsPrec :: Int -> TMCMD -> ShowS
$cshowsPrec :: Int -> TMCMD -> ShowS
Show, TMCMD -> TMCMD -> Bool
(TMCMD -> TMCMD -> Bool) -> (TMCMD -> TMCMD -> Bool) -> Eq TMCMD
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: TMCMD -> TMCMD -> Bool
$c/= :: TMCMD -> TMCMD -> Bool
== :: TMCMD -> TMCMD -> Bool
$c== :: TMCMD -> TMCMD -> Bool
Eq, Eq TMCMD
Eq TMCMD
-> (TMCMD -> TMCMD -> Ordering)
-> (TMCMD -> TMCMD -> Bool)
-> (TMCMD -> TMCMD -> Bool)
-> (TMCMD -> TMCMD -> Bool)
-> (TMCMD -> TMCMD -> Bool)
-> (TMCMD -> TMCMD -> TMCMD)
-> (TMCMD -> TMCMD -> TMCMD)
-> Ord TMCMD
TMCMD -> TMCMD -> Bool
TMCMD -> TMCMD -> Ordering
TMCMD -> TMCMD -> TMCMD
forall a.
Eq a
-> (a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
min :: TMCMD -> TMCMD -> TMCMD
$cmin :: TMCMD -> TMCMD -> TMCMD
max :: TMCMD -> TMCMD -> TMCMD
$cmax :: TMCMD -> TMCMD -> TMCMD
>= :: TMCMD -> TMCMD -> Bool
$c>= :: TMCMD -> TMCMD -> Bool
> :: TMCMD -> TMCMD -> Bool
$c> :: TMCMD -> TMCMD -> Bool
<= :: TMCMD -> TMCMD -> Bool
$c<= :: TMCMD -> TMCMD -> Bool
< :: TMCMD -> TMCMD -> Bool
$c< :: TMCMD -> TMCMD -> Bool
compare :: TMCMD -> TMCMD -> Ordering
$ccompare :: TMCMD -> TMCMD -> Ordering
$cp1Ord :: Eq TMCMD
Ord)

-- |'StateVal' represents belongnes of 'State' to tape, Turing machine commands and S-machine 'SM'.
data StateVal = StateVal {StateVal -> Int
tape :: Int, StateVal -> Maybe TMCMD
tmCommand :: Maybe TMCMD, StateVal -> Maybe SMTag
smTag :: Maybe SMTag}
   deriving (Int -> StateVal -> ShowS
[StateVal] -> ShowS
StateVal -> String
(Int -> StateVal -> ShowS)
-> (StateVal -> String) -> ([StateVal] -> ShowS) -> Show StateVal
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [StateVal] -> ShowS
$cshowList :: [StateVal] -> ShowS
show :: StateVal -> String
$cshow :: StateVal -> String
showsPrec :: Int -> StateVal -> ShowS
$cshowsPrec :: Int -> StateVal -> ShowS
Show, StateVal -> StateVal -> Bool
(StateVal -> StateVal -> Bool)
-> (StateVal -> StateVal -> Bool) -> Eq StateVal
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: StateVal -> StateVal -> Bool
$c/= :: StateVal -> StateVal -> Bool
== :: StateVal -> StateVal -> Bool
$c== :: StateVal -> StateVal -> Bool
Eq, Eq StateVal
Eq StateVal
-> (StateVal -> StateVal -> Ordering)
-> (StateVal -> StateVal -> Bool)
-> (StateVal -> StateVal -> Bool)
-> (StateVal -> StateVal -> Bool)
-> (StateVal -> StateVal -> Bool)
-> (StateVal -> StateVal -> StateVal)
-> (StateVal -> StateVal -> StateVal)
-> Ord StateVal
StateVal -> StateVal -> Bool
StateVal -> StateVal -> Ordering
StateVal -> StateVal -> StateVal
forall a.
Eq a
-> (a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
min :: StateVal -> StateVal -> StateVal
$cmin :: StateVal -> StateVal -> StateVal
max :: StateVal -> StateVal -> StateVal
$cmax :: StateVal -> StateVal -> StateVal
>= :: StateVal -> StateVal -> Bool
$c>= :: StateVal -> StateVal -> Bool
> :: StateVal -> StateVal -> Bool
$c> :: StateVal -> StateVal -> Bool
<= :: StateVal -> StateVal -> Bool
$c<= :: StateVal -> StateVal -> Bool
< :: StateVal -> StateVal -> Bool
$c< :: StateVal -> StateVal -> Bool
compare :: StateVal -> StateVal -> Ordering
$ccompare :: StateVal -> StateVal -> Ordering
$cp1Ord :: Eq StateVal
Ord)

-- |This data type represents state of S-machine 'SM'. 
--
-- 's_name' represents a name of 'State'.
--
-- 's_idx' represents a low index of 'State'.
--
-- 's_tags' represents a set of 'Tag' of 'State'.
--
-- 's_val' represents a 'StateVal' of 'State'.
data State = State {State -> StateName
s_name :: StateName, State -> String
s_idx :: String, State -> Set Tag
s_tags :: Set Tag, State -> Maybe StateVal
s_val :: Maybe StateVal}
   deriving (Int -> State -> ShowS
[State] -> ShowS
State -> String
(Int -> State -> ShowS)
-> (State -> String) -> ([State] -> ShowS) -> Show State
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [State] -> ShowS
$cshowList :: [State] -> ShowS
show :: State -> String
$cshow :: State -> String
showsPrec :: Int -> State -> ShowS
$cshowsPrec :: Int -> State -> ShowS
Show, Eq State
Eq State
-> (State -> State -> Ordering)
-> (State -> State -> Bool)
-> (State -> State -> Bool)
-> (State -> State -> Bool)
-> (State -> State -> Bool)
-> (State -> State -> State)
-> (State -> State -> State)
-> Ord State
State -> State -> Bool
State -> State -> Ordering
State -> State -> State
forall a.
Eq a
-> (a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
min :: State -> State -> State
$cmin :: State -> State -> State
max :: State -> State -> State
$cmax :: State -> State -> State
>= :: State -> State -> Bool
$c>= :: State -> State -> Bool
> :: State -> State -> Bool
$c> :: State -> State -> Bool
<= :: State -> State -> Bool
$c<= :: State -> State -> Bool
< :: State -> State -> Bool
$c< :: State -> State -> Bool
compare :: State -> State -> Ordering
$ccompare :: State -> State -> Ordering
$cp1Ord :: Eq State
Ord, State -> State -> Bool
(State -> State -> Bool) -> (State -> State -> Bool) -> Eq State
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: State -> State -> Bool
$c/= :: State -> State -> Bool
== :: State -> State -> Bool
$c== :: State -> State -> Bool
Eq)

-- |This data type represents a tape letter of S-machine 'SM'.
data Y = Y Square | Alpha | Delta | Omega
   deriving (Int -> Y -> ShowS
[Y] -> ShowS
Y -> String
(Int -> Y -> ShowS) -> (Y -> String) -> ([Y] -> ShowS) -> Show Y
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [Y] -> ShowS
$cshowList :: [Y] -> ShowS
show :: Y -> String
$cshow :: Y -> String
showsPrec :: Int -> Y -> ShowS
$cshowsPrec :: Int -> Y -> ShowS
Show, Y -> Y -> Bool
(Y -> Y -> Bool) -> (Y -> Y -> Bool) -> Eq Y
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: Y -> Y -> Bool
$c/= :: Y -> Y -> Bool
== :: Y -> Y -> Bool
$c== :: Y -> Y -> Bool
Eq, Eq Y
Eq Y
-> (Y -> Y -> Ordering)
-> (Y -> Y -> Bool)
-> (Y -> Y -> Bool)
-> (Y -> Y -> Bool)
-> (Y -> Y -> Bool)
-> (Y -> Y -> Y)
-> (Y -> Y -> Y)
-> Ord Y
Y -> Y -> Bool
Y -> Y -> Ordering
Y -> Y -> Y
forall a.
Eq a
-> (a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
min :: Y -> Y -> Y
$cmin :: Y -> Y -> Y
max :: Y -> Y -> Y
$cmax :: Y -> Y -> Y
>= :: Y -> Y -> Bool
$c>= :: Y -> Y -> Bool
> :: Y -> Y -> Bool
$c> :: Y -> Y -> Bool
<= :: Y -> Y -> Bool
$c<= :: Y -> Y -> Bool
< :: Y -> Y -> Bool
$c< :: Y -> Y -> Bool
compare :: Y -> Y -> Ordering
$ccompare :: Y -> Y -> Ordering
$cp1Ord :: Eq Y
Ord)

-- |This is a data type of symbols that can be on 'SM' tape.
--
-- Symbols can be 'Y' ('SmbY'), its invertions ('SmbY'') and 'State' ('SmbQ').
data Smb = SmbY Y | SmbY' Y | SmbQ State
   deriving (Smb -> Smb -> Bool
(Smb -> Smb -> Bool) -> (Smb -> Smb -> Bool) -> Eq Smb
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: Smb -> Smb -> Bool
$c/= :: Smb -> Smb -> Bool
== :: Smb -> Smb -> Bool
$c== :: Smb -> Smb -> Bool
Eq, Eq Smb
Eq Smb
-> (Smb -> Smb -> Ordering)
-> (Smb -> Smb -> Bool)
-> (Smb -> Smb -> Bool)
-> (Smb -> Smb -> Bool)
-> (Smb -> Smb -> Bool)
-> (Smb -> Smb -> Smb)
-> (Smb -> Smb -> Smb)
-> Ord Smb
Smb -> Smb -> Bool
Smb -> Smb -> Ordering
Smb -> Smb -> Smb
forall a.
Eq a
-> (a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
min :: Smb -> Smb -> Smb
$cmin :: Smb -> Smb -> Smb
max :: Smb -> Smb -> Smb
$cmax :: Smb -> Smb -> Smb
>= :: Smb -> Smb -> Bool
$c>= :: Smb -> Smb -> Bool
> :: Smb -> Smb -> Bool
$c> :: Smb -> Smb -> Bool
<= :: Smb -> Smb -> Bool
$c<= :: Smb -> Smb -> Bool
< :: Smb -> Smb -> Bool
$c< :: Smb -> Smb -> Bool
compare :: Smb -> Smb -> Ordering
$ccompare :: Smb -> Smb -> Ordering
$cp1Ord :: Eq Smb
Ord)

instance Show Smb where
   show :: Smb -> String
show (SmbY Y
y) = Y -> String
forall a. Show a => a -> String
show Y
y
   show (SmbY' Y
y) = Y -> String
forall a. Show a => a -> String
show Y
y String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
"^{-1}"
   show (SmbQ State
q) = State -> String
forall a. Show a => a -> String
show State
q

-- |This is a admissible word of the S-machine 'SM', which consist of the 'Smb'.
newtype Word = Word [Smb]
   deriving (Int -> Word -> ShowS
[Word] -> ShowS
Word -> String
(Int -> Word -> ShowS)
-> (Word -> String) -> ([Word] -> ShowS) -> Show Word
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [Word] -> ShowS
$cshowList :: [Word] -> ShowS
show :: Word -> String
$cshow :: Word -> String
showsPrec :: Int -> Word -> ShowS
$cshowsPrec :: Int -> Word -> ShowS
Show, Word -> Word -> Bool
(Word -> Word -> Bool) -> (Word -> Word -> Bool) -> Eq Word
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: Word -> Word -> Bool
$c/= :: Word -> Word -> Bool
== :: Word -> Word -> Bool
$c== :: Word -> Word -> Bool
Eq, Eq Word
Eq Word
-> (Word -> Word -> Ordering)
-> (Word -> Word -> Bool)
-> (Word -> Word -> Bool)
-> (Word -> Word -> Bool)
-> (Word -> Word -> Bool)
-> (Word -> Word -> Word)
-> (Word -> Word -> Word)
-> Ord Word
Word -> Word -> Bool
Word -> Word -> Ordering
Word -> Word -> Word
forall a.
Eq a
-> (a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
min :: Word -> Word -> Word
$cmin :: Word -> Word -> Word
max :: Word -> Word -> Word
$cmax :: Word -> Word -> Word
>= :: Word -> Word -> Bool
$c>= :: Word -> Word -> Bool
> :: Word -> Word -> Bool
$c> :: Word -> Word -> Bool
<= :: Word -> Word -> Bool
$c<= :: Word -> Word -> Bool
< :: Word -> Word -> Bool
$c< :: Word -> Word -> Bool
compare :: Word -> Word -> Ordering
$ccompare :: Word -> Word -> Ordering
$cp1Ord :: Eq Word
Ord)

-- |This is a rule of the S-machine 'SM'. 
--
-- Left part of the pair represents what substitute.
--
-- Right part -- for what substitute.
newtype SRule = SRule [(Word, Word)]
   deriving (SRule -> SRule -> Bool
(SRule -> SRule -> Bool) -> (SRule -> SRule -> Bool) -> Eq SRule
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: SRule -> SRule -> Bool
$c/= :: SRule -> SRule -> Bool
== :: SRule -> SRule -> Bool
$c== :: SRule -> SRule -> Bool
Eq, Eq SRule
Eq SRule
-> (SRule -> SRule -> Ordering)
-> (SRule -> SRule -> Bool)
-> (SRule -> SRule -> Bool)
-> (SRule -> SRule -> Bool)
-> (SRule -> SRule -> Bool)
-> (SRule -> SRule -> SRule)
-> (SRule -> SRule -> SRule)
-> Ord SRule
SRule -> SRule -> Bool
SRule -> SRule -> Ordering
SRule -> SRule -> SRule
forall a.
Eq a
-> (a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
min :: SRule -> SRule -> SRule
$cmin :: SRule -> SRule -> SRule
max :: SRule -> SRule -> SRule
$cmax :: SRule -> SRule -> SRule
>= :: SRule -> SRule -> Bool
$c>= :: SRule -> SRule -> Bool
> :: SRule -> SRule -> Bool
$c> :: SRule -> SRule -> Bool
<= :: SRule -> SRule -> Bool
$c<= :: SRule -> SRule -> Bool
< :: SRule -> SRule -> Bool
$c< :: SRule -> SRule -> Bool
compare :: SRule -> SRule -> Ordering
$ccompare :: SRule -> SRule -> Ordering
$cp1Ord :: Eq SRule
Ord)

instance Show SRule where
   show :: SRule -> String
show (SRule [(Word, Word)]
s) = String
"[" String -> ShowS
forall a. [a] -> [a] -> [a]
++ ((Word, Word) -> ShowS) -> String -> [(Word, Word)] -> String
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr (\(Word
w1,Word
w2) String
acc -> Word -> String
forall a. Show a => a -> String
show Word
w1 String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
"->" String -> ShowS
forall a. [a] -> [a] -> [a]
++ Word -> String
forall a. Show a => a -> String
show Word
w2 String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
";" String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
acc) String
"" [(Word, Word)]
s String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
"]\n"

-- |This is data type of S-machine.
--
-- It consists of a lists of tape letters 'Y', states 'State' and rules 'SRule'.
data SM =  SM {SM -> [[Y]]
yn :: [[Y]], SM -> [Set State]
qn :: [Set State], SM -> [SRule]
srs :: [SRule]} deriving (Int -> SM -> ShowS
[SM] -> ShowS
SM -> String
(Int -> SM -> ShowS)
-> (SM -> String) -> ([SM] -> ShowS) -> Show SM
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [SM] -> ShowS
$cshowList :: [SM] -> ShowS
show :: SM -> String
$cshow :: SM -> String
showsPrec :: Int -> SM -> ShowS
$cshowsPrec :: Int -> SM -> ShowS
Show, SM -> SM -> Bool
(SM -> SM -> Bool) -> (SM -> SM -> Bool) -> Eq SM
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: SM -> SM -> Bool
$c/= :: SM -> SM -> Bool
== :: SM -> SM -> Bool
$c== :: SM -> SM -> Bool
Eq, Eq SM
Eq SM
-> (SM -> SM -> Ordering)
-> (SM -> SM -> Bool)
-> (SM -> SM -> Bool)
-> (SM -> SM -> Bool)
-> (SM -> SM -> Bool)
-> (SM -> SM -> SM)
-> (SM -> SM -> SM)
-> Ord SM
SM -> SM -> Bool
SM -> SM -> Ordering
SM -> SM -> SM
forall a.
Eq a
-> (a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
min :: SM -> SM -> SM
$cmin :: SM -> SM -> SM
max :: SM -> SM -> SM
$cmax :: SM -> SM -> SM
>= :: SM -> SM -> Bool
$c>= :: SM -> SM -> Bool
> :: SM -> SM -> Bool
$c> :: SM -> SM -> Bool
<= :: SM -> SM -> Bool
$c<= :: SM -> SM -> Bool
< :: SM -> SM -> Bool
$c< :: SM -> SM -> Bool
compare :: SM -> SM -> Ordering
$ccompare :: SM -> SM -> Ordering
$cp1Ord :: Eq SM
Ord)