Functional programming and stateful algorithms
- by bigstones
I'm learning functional programming with Haskell. In the meantime I'm studying Automata theory and as the two seem to fit well together I'm writing a small library to play with automata.
Here's the problem that made me ask the question. While studying a way to evaluate a state's reachability I got the idea that a simple recursive algorithm would be quite inefficient, because some paths might share some states and I might end up evaluating them more than once.
For example, here, evaluating reachability of g from a, I'd have to exclude f both while checking the path through d and c:
So my idea is that an algorithm working in parallel on many paths and updating a shared record of excluded states might be great, but that's too much for me.
I've seen that in some simple recursion cases one can pass state as an argument, and that's what I have to do here, because I pass forward the list of states I've gone through to avoid loops. But is there a way to pass that list also backwards, like returning it in a tuple together with the boolean result of my canReach function? (although this feels a bit forced)
Besides the validity of my example case, what other techniques are available to solve this kind of problems? I feel like these must be common enough that there have to be solutions like what happens with fold* or map.
So far, reading learnyouahaskell.com I didn't find any, but consider I haven't touched monads yet.
(if interested, I posted my code on codereview)
