[Haskell-cafe] Encoding for flow charts
Richard Wallace
rwallace at thewallacepack.net
Thu Dec 25 23:34:19 UTC 2014
Hello,
I've been working to encode a fairly complex flow chart. At first I took
the simple approach of having a single data type for the possible states
data S = S0 | S1 | S2
and then a simple recursive function to step through it
loop :: Monad m => S -> StateT s m Result
loop S0 = testS0 >>= \r -> if r then loop S1 else loop S2
loop S1 = s1Result
loop S2 = s2Result
This works well enough, but with the size of the flow chart I'm working
with (50+ decision points) it quickly becomes clear that it's probably not
the most best way to do it. One problem that I'd like to solve is being
able to test each decision point in isolation, making sure that decision
point `m` will go to decision point `n` when it is supposed to, without
having to run through the whole rest of the flow chart that would otherwise
follow. Something else I'd like to achieve is being able to organize the
decisions into separate modules - much better than having just the one big
function above.
Here's what I've come up with as an alternative so far.
data Step a b where
TrueFlow :: Decision a d e => a -> Step a b
FalseFlow :: Decision b f g => b -> Step a b
Done :: Result -> Step a b
class Decision a b c | a -> b, a -> c where
decide :: (Functor m, Monad m) => a -> StateT s m (Step b c)
data S0 = S0 deriving (Show, Eq)
instance Decision S0 S1 S2 where
decide _ = bool (FalseFlow S2) (TrueFlow S1) <$> testS0
data S1 = S1 deriving (Show, Eq)
instance Decision S1 () () where
decide _ = s1Result
data S2 = S2 deriving (Show, Eq)
instance Decision S2 () () where
decide _ = s2Result
decision :: (Functor m, Monad m, Decision a b c)
=> a
-> StateT s m Result
decision s = decide s >>= \case
TrueFlow b -> decision b
FalseFlow c -> decision c
Done s -> return s
With this implementation it is easy to test a single decision point, - just
use `evalStateT (decide S0) s` and compare the resulting Step to make sure
it is either S1 or S2. The logic can also be easily separated and
organized into modules.
The biggest drawback of this new approach is the need to create a new
`Step` record at every decision point. In the end, this may be worth it
for the added design benefits, but would love to be able to get rid of it
and find a solution that gives the added benefits without incurring any
performance penalties.
Any suggestions anyone can give on improvements would be greatly
appreciated.
Thanks!
Rich
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20141225/0c4c3b88/attachment.html>
More information about the Haskell-Cafe
mailing list