Как обычно, несмотря на прекрасные ответы, которые уже присутствовали, я не мог удержаться, чтобы попробовать это для себя.Одна вещь, которая беспокоила меня о том, что представлено, это то, что он игнорирует ввод.Конечные автоматы - те, с которыми я знаком, - выбирают между различными возможными переходами на основе ввода.
data State vocab = State { stateId :: String
, possibleInputs :: [vocab]
, _runTrans :: (vocab -> State vocab)
}
| GoalState { stateId :: String }
instance Show (State a) where
show = stateId
runTransition :: Eq vocab => State vocab -> vocab -> Maybe (State vocab)
runTransition (GoalState id) _ = Nothing
runTransition s x | x `notElem` possibleInputs s = Nothing
| otherwise = Just (_runTrans s x)
Здесь я определяю тип State, который параметризуется типом словаря vocab,Теперь давайте определим способ, которым мы можем отслеживать выполнение конечного автомата путем подачи его входных данных.
traceMachine :: (Show vocab, Eq vocab) => State vocab -> [vocab] -> IO ()
traceMachine _ [] = putStrLn "End of input"
traceMachine s (x:xs) = do
putStrLn "Current state: "
print s
putStrLn "Current input: "
print x
putStrLn "-----------------------"
case runTransition s x of
Nothing -> putStrLn "Invalid transition"
Just s' -> case s' of
goal@(GoalState _) -> do
putStrLn "Goal state reached:"
print s'
putStrLn "Input remaining:"
print xs
_ -> traceMachine s' xs
Теперь давайте попробуем это на простой машине, которая игнорирует его входные данные.Будьте осторожны: формат, который я выбрал, довольно многословен.Тем не менее, каждая последующая функция может рассматриваться как узел на диаграмме конечного автомата, и я думаю, вы найдете, что многословие полностью соответствует описанию такого узла.Я использовал stateId для кодирования в строковом формате некоторой визуальной информации о том, как ведет себя это состояние.
data SimpleVocab = A | B | C deriving (Eq, Ord, Show, Enum)
simpleMachine :: State SimpleVocab
simpleMachine = stateA
stateA :: State SimpleVocab
stateA = State { stateId = "A state. * -> B"
, possibleInputs = [A,B,C]
, _runTrans = \_ -> stateB
}
stateB :: State SimpleVocab
stateB = State { stateId = "B state. * -> C"
, possibleInputs = [A,B,C]
, _runTrans = \_ -> stateC
}
stateC :: State SimpleVocab
stateC = State { stateId = "C state. * -> A"
, possibleInputs = [A,B,C]
, _runTrans = \_ -> stateA
}
Поскольку входные данные не имеют значения для этого конечного автомата, вы можете передать ему что угодно.
ghci> traceMachine simpleMachine [A,A,A,A]
Я не буду включать вывод, который также очень многословен, но вы можете видеть, что он явно перемещается от stateA к stateB до stateC и обратно к stateA снова.Теперь давайте сделаем немного более сложную машину:
lessSimpleMachine :: State SimpleVocab
lessSimpleMachine = startNode
startNode :: State SimpleVocab
startNode = State { stateId = "Start node. A -> 1, C -> 2"
, possibleInputs = [A,C]
, _runTrans = startNodeTrans
}
where startNodeTrans C = node2
startNodeTrans A = node1
node1 :: State SimpleVocab
node1 = State { stateId = "node1. B -> start, A -> goal"
, possibleInputs = [B, A]
, _runTrans = node1trans
}
where node1trans B = startNode
node1trans A = goalNode
node2 :: State SimpleVocab
node2 = State { stateId = "node2. C -> goal, A -> 1, B -> 2"
, possibleInputs = [A,B,C]
, _runTrans = node2trans
}
where node2trans A = node1
node2trans B = node2
node2trans C = goalNode
goalNode :: State SimpleVocab
goalNode = GoalState "Goal. :)"
Возможные входы и переходы для каждого узла не должны требовать дополнительных пояснений, так как они подробно описаны в коде.Я позволю тебе поиграть с traceMachine lessSipmleMachine inputs для себя.Посмотрите, что происходит, когда inputs недопустимо (не соответствует ограничениям «возможных входов»), или когда вы достигаете целевого узла до конца ввода.
Полагаю, многословность моего решения вродене соответствует тому, что вы в основном просили, что должно было сократить расходы.Но я думаю, что это также иллюстрирует, каким может быть описательный код на Haskell.Несмотря на то, что он очень многословен, он также очень прост в том, как он представляет узлы диаграммы конечного автомата.