[Haskell-cafe] Encoding for flow charts

Richard Wallace rwallace at thewallacepack.net
Thu Dec 25 23:34:19 UTC 2014


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

-------------- 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