I am going to split this answer into two parts. The first part will answer your initial question, and the second part will answer the FSA non-deterministic question that you raised in the comments.
Pipes
You can use pipes to alternate effects between calculations. First, I'll start with a slightly modified version of your code:
data FA ns = 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
The only difference is that I use an enumeration instead of a String for State .
Then I will perform your transitions as a Pipe :
runFA :: (Monad m, Proxy p) => FA ns -> () -> Pipe (StateP np) snmr runFA (FA _ _ trans) () = forever $ do s <- request () n <- get put (trans ns) respond n
Look carefully at the type of Pipe :
() -> Pipe (StateP np) snmr ^ ^ ^ | | | 'n' is the state -+ | | | | 's come in -+ +- 'n go out
So you can think of it as an effective scanl . It receives stream s using request and outputs stream n using respond . It can actually alternate effects directly if we want, but instead I will transfer external effects to other processing steps.
When we formulate it as a Pipe , we have the luxury of choosing what our input and output flows will be. For example, we can connect the input to an unclean stdin and connect the output to an unclean stdout :
import Control.Proxy import Control.Proxy.Trans.State main = runProxy $ execStateK (initSt1 fa) $ stdinS >-> takeWhileD (/= "quit") >-> mapD read >-> runFA fa >-> printD
This is a processing pipeline that you can read:
- Run the following
Pipe with the initial state of initSt - Flow Values from Standard Input
- Keep streaming until one of these values is
"quit" - Apply
read to all values to convert them to Trans es - Run them through our scanning state machine
- Print
State , which the machine emits
Try:
>>> main A S1 B S2 C S3 A S1 quit S2 >>>
Notice how it also returns the final State in which our machine was located. Then you could fmap check your test for this calculation to see if it ended with the node terminal:
>>> fmap (`elem` [S1, S2]) main A S1 B S2 C S3 A S1 quit True
In addition, we can connect our machine to clean inputs and outputs:
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
This pipeline says:
- Run this in a clean calculation (i.e., `runIdentity) and print a clean result
- Use
Writer to register all the states we visited. - Use
State to track the current state. - Provide a list of predefined transitions cleanly
- Run these transitions through our FSA
- Write outputs in
Writer using liftP to indicate that we are targeting Writer
Try also:
>>> main (S2,[S1,S2,S4,S1])
This displays the final state and a list of visited states.
Listt
Now, you have raised the second question of how you do efficient non-deterministic calculations. Daniel was actually wrong: you can alternate effects without determinism with pipes too! The trick is to use ProduceT , which is a pipes implementation of ListT .
First I will show how to use 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'
The code above says:
- Print Current Status
- Bind many possible transitions non-deterministically
- Returns the new selected state
To avoid passing state manually, I will fsa in 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'
Now I can easily run the generator on several transitions using mapM . When I'm done, I will compile it with Producer using 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
This creates a channel, the effects of which should print the states that it passes through and displays a stream of final states that it encounters. I will connect the output to the printing phase so that we can observe both at the same time:
>>> 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
We can observe the path of the machine that he takes and how he retreats. He prints the exits, where he is currently after each step, and then emits all 7 of his final states as soon as he arrives at them.
Sorry if this post is a little unpolished, but this is the best I can do in a hurry.