6

我的问题的要点是我有一个确定性状态自动机，它根据移动列表进行转换，我希望这个转换序列用作另一个函数的“计算上下文”。这个另一个函数会在每次转换时观察状态机，并用它做一些计算，这让人联想到模型视图模式。简单地说，这个其他功能可能只是读取机器的当前状态，并将其打印到屏幕上。

我的状态机实现：

data FA n s = FA { initSt1 :: n, endSt1 :: [n], trans1 :: n -> s -> n }

-- | Checks if sequence of transitions arrives at terminal nodes
evalFA :: Eq n => FA n s -> [s] -> Bool
evalFA fa@(FA _ sfs _ ) = (`elem` sfs) . (runFA fa)

-- | Outputs final state reached by sequence of transitons
runFA :: FA n s -> [s] -> n
runFA (FA s0 sfs trans) = foldl trans s0

和例子：

type State = String
data Trans = A | B | C | D | E

fa :: FA State Trans
fa = FA ("S1") ["S4","S5"] t1

-- | Note non-matched transitions automatically goes to s0
t1 :: State -> Trans -> State
t1 "S1" E = "S1"
t1 "S1" A = "S2"
t1 "S2" B = "S3"
t1 "S2" C = "S4"
t1 "S3" D = "S5"
t1 _  _   = "S1"

runFA fa [A,B]   -- | S3
4

1 回答 1

9

我将把这个答案分成两部分。第一部分将回答您最初的问题，第二部分将回答您在评论中提出的非确定性 FSA 问题。

管道

您可以使用pipes在计算之间交错效果。首先，我将从您的代码稍作修改的版本开始：

data FA n s = FA { initSt1 :: n, endSt1 :: [n], trans1 :: n -> s -> n }

data State = S1 | S2 | S3 | S4 | S5 deriving (Eq, Show)
data Trans = A | B | C | D | E deriving (Read)

fa :: FA State Trans
fa = FA (S1) [S4,S5] t1

-- | Note non-matched transitions automatically goes to s0
t1 :: State -> Trans -> State
t1 S1 E = S1
t1 S1 A = S2
t1 S2 B = S3
t1 S2 C = S4
t1 S3 D = S5
t1 _  _ = S1

唯一的区别是我使用枚举而不是String.State

接下来，我会将您的转换实现为Pipe：

runFA :: (Monad m, Proxy p) => FA n s -> () -> Pipe (StateP n p) s n m r
runFA (FA _ _ trans) () = forever $ do
    s <- request ()
    n <- get
    put (trans n s)
    respond n

让我们仔细看看 的类型Pipe：

() -> Pipe (StateP n p) s n m r
                   ^    ^ ^
                   |    | |
 'n' is the state -+    | |
                        | |
          's's come in -+ +- 'n's go out

所以你可以认为这是一个有效的scanl. 它接收一个ss 的流 usingrequest并输出一个ns 的流 using respond。如果我们愿意，它实际上可以直接交错效果，但我会将效果外包给其他处理阶段。

当我们将其表述为 时Pipe，我们可以选择输入和输出流是什么。例如，我们可以将输入连接到 impurestdin并将输出连接到 impure stdout：

import Control.Proxy
import Control.Proxy.Trans.State

main = runProxy $ execStateK (initSt1 fa) $
    stdinS >-> takeWhileD (/= "quit") >-> mapD read >-> runFA fa >-> printD

这是一个处理管道，您可以将其解读为：

  • Pipe以初始状态执行以下操作initSt
  • 来自标准输入的流值
  • 继续流式传输，直到其中一个值是"quit"
  • 应用于read所有值以将它们转换为Transes
  • 通过我们的扫描有限状态自动机运行它们
  • 打印State自动机发出的 s

让我们尝试一下：

>>> main
A
S1
B
S2
C
S3
A
S1
quit
S2
>>>

请注意它如何返回State我们的自动机所在的最终结果。然后fmap您可以测试此计算以查看它是否以终端节点结束：

>>> fmap (`elem` [S1, S2]) main
A
S1
B
S2
C
S3
A
S1
quit
True

或者，我们也可以将我们的自动机连接到纯输入和输出：

import Control.Proxy.Trans.Writer
import Data.Functor.Identity

main = print $ runIdentity $ runProxy $ runWriterK $ execStateK (initSt1 fa) $
    fromListS [A, C, E, A] >-> runFA fa >-> liftP . toListD

该管道说：

  • 在纯计算（即`runIdentity）中运行它并打印纯结果
  • 用于Writer记录我们访问过的所有状态
  • 用于State跟踪我们当前的状态
  • 纯粹提供预定义转换列表
  • 通过我们的 FSA 运行这些过渡
  • 将输出记录到Writer，liftP用于指定我们的目标Writer

我们也试试这个：

>>> main
(S2,[S1,S2,S4,S1])

输出最终状态和访问状态列表。

列表T

现在，您提出了第二个问题，即如何进行有效的非确定性计算。丹尼尔实际上是不正确的：您也可以使用 来将效果与不确定性交错pipes！诀窍是使用ProduceT，也就是pipes实现ListT。

首先，我将展示如何使用ProduceT：

fsa :: (Proxy p) => State -> Trans -> ProduceT p IO State
fsa state trans = do
    lift $ putStrLn $ "At State: " ++ show state
    state' <- eachS $ case (state, trans) of
        (S1, A) -> [S2, S3]
        (S2, B) -> [S4, S5]
        (S3, B) -> [S5, S2]
        (S4, C) -> [S2, S3]
        (S5, C) -> [S3, S4]
        (_ , _) -> [S1]
    return state'

上面的代码说：

  • 打印当前状态
  • 非确定性地绑定许多可能的转换
  • 返回新的选中状态

为避免手动状态传递，我将换fsa行StateT：

import qualified Control.Monad.Trans.State as S

fsa2 :: (Proxy p) => Trans -> S.StateT State (ProduceT p IO) State
fsa2 trans = do
    s <- S.get
    s' <- lift $ fsa s trans
    S.put s'
    return s'

现在我可以使用mapM. 完成后，我将其编译为Producerusing runRespondT：

use1 :: (Proxy p) => () -> Producer p State IO ()
use1 () = runRespondT $ (`S.execStateT` S1) $ do
    mapM_ fsa2 [A, B, C]  -- Run the generator using four transitions

这会产生一个管道，其效果是打印它正在遍历的状态，并输出它遇到的最终状态流。我将输出连接到打印阶段，以便我们可以同时观察两者：

>>> runProxy $ use1 >-> printD
At State: S1
At State: S2
At State: S4
S2
S3
At State: S5
S3
S4
At State: S3
At State: S5
S3
S4
At State: S2
S1

我们可以观察自动机的路径以及它是如何回溯的。它在每一步之后打印出它当前的位置，然后在到达它们时立即发出所有 7 个最终状态。

对不起，如果这篇文章有点粗糙，但这是我能尽快做的最好的。

于 2013-05-16T15:29:22.970 回答