[Haskell-cafe] Encoding for flow charts

[Stephen Tetley]

Hi Richard

It might be worth looking at Wyatt Allan and Martin Erwig's Surveyor
DSEL for alternative design ideas. The authors directly encode
questions rather than states which, without looking closely, seems
more natural to me - I think you could envisage flow diagrams as
specializations of "surveys".

The paper is available from Martin's website:

http://web.engr.oregonstate.edu/~erwig/papers/abstracts.html

Best wishes

Stephen

On 25 December 2014 at 23:34, Richard Wallace
<rwallace at thewallacepack.net> wrote:
> 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
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>