-- Implementación de Máquina de Turing

-- Se define formalmente como TM  = (Q, Σ, Γ, δ, qo, ␣, F) donde:
-- Q Conjunto de estados
-- Σ Alfabeto de entrada
-- Γ Alfabeto de la cinta
-- δ Función de transición
-- q0 Estado Inicial
-- ␣ Símbolo en blanco
-- F Conjunto de estados finales

-- Definamos los tipos:

type State = String

-- Una configuración se representa mediante el siguiente sinónimo
-- El entero representa la posición de la cabeza de lectoescritura en la cadena
type Config = (State, String, Int)

type Q = [State]
type Sigma = [Char]
type Gamma = [Char]
type Delta = State -> Char -> (State, Char, Movement)
type F = [String]

-- Movimiento de la cabeza lectora
data Movement = L | R

-- Tipo de dato algebraico de la Máquina de Turing
data MaqT = MaqT { states :: Q
                 , sigma :: Sigma
                 , gamma :: Gamma
                 , delta :: Delta
                 , q_0 :: State
                 , blank_symbol :: Char
                 , end_states :: F
                 }

-- Recibe una MaqT y una cadena
-- Imprime el procesamiento formal de la cadena con configuraciones
compute :: MaqT -> String -> [Config]
compute tm@(MaqT _ _ _ _ q_0 blank_symbol _) str = computeAux tm q_0 aux_str 0
    where aux_str = str ++ [blank_symbol, blank_symbol]

computeAux :: MaqT -> State -> String -> Int -> [Config]
computeAux tm@(MaqT states sigma gamma delta _ blank_symbol end_states) q str index =
    if index == (length str)
    then []
    else    let (q_next, c_next, mov) = delta q (str !! index)
                new_str = replaceNth index c_next str
                i_head = case mov of
                        L -> index - 1
                        R -> index + 1
                formatted_str = [ x | x <- str, not (x `elem` [blank_symbol]) ]
                config = (q, formatted_str, index)
            in if q `elem` end_states
                then config:[]
                else config:(computeAux tm q_next new_str i_head)


replaceNth :: Int -> a -> [a] -> [a]
replaceNth _ _ [] = []
replaceNth n newVal (x:xs)
    | n == 0 = newVal:xs
    | otherwise = x:replaceNth (n-1) newVal xs

-- Recibe una MaqT y una cadena
-- Regresa un bool diciendo si la cadena es aceptada [true] o no [false]
-- por la máquina de Turing
accept :: MaqT -> String -> Bool
accept _ _ = True

-- Recibe una MaqT
-- Codifica la MaqT para pasarla como entrada de la Máquina Universal
encode :: MaqT -> String
encode _ = "d"

-- EXTRA

-- Recibe una String representando una máquina codificada
-- Regresa la MaqT que representa
decode :: String -> MaqT
decode _ = error "sdf"

tm_delta :: State -> Char -> (State, Char, Movement)
tm_delta "q0" 'a' = ("q1", 'A', R)
tm_delta "q0" 'B' = ("q4", 'B', R)

tm_delta "q1" 'a' = ("q1", 'a', R)
tm_delta "q1" 'b' = ("q2", 'B', R)
tm_delta "q1" 'B' = ("q1", 'B', R)

tm_delta "q2" 'C' = ("q2", 'C', R)
tm_delta "q2" 'b' = ("q2", 'b', R)
tm_delta "q2" 'c' = ("q3", 'C', L)

tm_delta "q3" 'A' = ("q0", 'A', R)
tm_delta "q3" 'C' = ("q3", 'C', L)
tm_delta "q3" 'b' = ("q3", 'b', L)
tm_delta "q3" 'B' = ("q3", 'B', L)
tm_delta "q3" 'a' = ("q3", 'a', L)

tm_delta "q4" 'B' = ("q4", 'B', R)
tm_delta "q4" 'C' = ("q4", 'C', R)
tm_delta "q4" '_' = ("qf", '_', R)

-- tm_delta _ _ = ("qf", '_', R)

tm_ex = MaqT { states=["q0", "q1", "q2", "q3", "q4", "qf"]
             , sigma=['a', 'b', 'c']
             , gamma=['a', 'b', 'c', 'A', 'B', 'C', '_']
             , delta=tm_delta
             , q_0="q0"
             , blank_symbol='_'
             , end_states=["qf"]
             }