# Functional programming and stateful algorithms

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

(if interested, I posted my code on codereview)

• I, for one, would love to see the code that you've been trying to work with. In the absence of that, my best advice is that Haskell's laziness can often be exploited to not compute things more than once. Look into so-called "tying the knot" and lazy value recursion, although your problem is likely simple enough that the more advanced techniques that take advantage of infinite values and similar things would be overkill, and would probably just confuse you right now. Oct 4, 2013 at 23:08
• @Ptharien'sFlame thank you for your interest! here's the code, there is also a link to the whole project. I'm already confused with what I've done so far, so yes, better not to look into advanced techniques :) Oct 4, 2013 at 23:40
• A state automata is pretty much the antithesis of functional programming. Functional programming is about solving problems without internal state, while a state automata is all about managing its own state. Oct 4, 2013 at 23:50
• @Philipp I disagree. An automaton or state machine is sometimes the most natural and accurate way to represent a problem, and functional automata are well studied. Oct 5, 2013 at 1:26
• @Philipp: functional programming is about making state explicit, not about forbidding it. In fact, tail recursion is a really great tool for implementing those state machines full of gotos. Oct 5, 2013 at 15:21

Functional programming doesn't get rid of state. It only makes it explicit! While it's true that functions like map will often "unravel" a "shared" data structure, if all you want to do is write a reachability algorithm then it's just a matter of keeping track of what nodes you already visited:

``````import qualified Data.Set as S
data Node = Node Int [Node] deriving (Show)

-- Receives a root node, returns a list of the node keyss visited in a depth-first search
dfs :: Node -> [Int]
dfs x = fst (dfs' (x, S.empty))

-- This worker function keeps track of a set of already-visited nodes to ignore.
dfs' :: (Node, S.Set Int) -> ([Int], S.Set Int)
dfs' (node@(Node k ns), s )
| k  `S.member` s = ([], s)
| otherwise =
let (childtrees, s') = loopChildren ns (S.insert k s) in
(k:(concat childtrees), s')

--This function could probably be implemented as just a fold but Im lazy today...
loopChildren :: [Node] -> S.Set Int -> ([[Int]], S.Set Int)
loopChildren []  s = ([], s)
loopChildren (n:ns) s =
let (xs, s') = dfs' (n, s) in
let (xss, s'') = loopChildren ns s' in
(xs:xss, s'')

na = Node 1 [nb, nc, nd]
nb = Node 2 [ne]
nc = Node 3 [ne, nf]
nd = Node 4 [nf]
ne = Node 5 [ng]
nf = Node 6 []
ng = Node 7 []

main = print \$ dfs na -- [1,2,5,7,3,6,4]
``````

Now, I must confess that keeping track of all this state by hand is pretty annoying and error prone (it's easy to use s' instead of s'', it's easy to pass the same s' to more than one computation...). This is where monads come in: they don't add anything you couldn't already do before but they let you pass the state variable around implicitly and the interface guarantees that it happens in a single-threaded manner.

Edit: I'll attempt to give a more reasoning of what I did now: first of all, instead of just testing for reachability I coded a depth-first search. The implementation is going to look pretty much the same but the debugging looks a bit better.

In a stateful language, the DFS would look kind of like this:

``````visited = set()  #mutable state
visitlist = []   #mutable state
def dfs(node):
if isMember(node, visited):
//do nothing
else:
visited[node.key] = true
visitlist.append(node.key)
for child in node.children:
dfs(child)
``````

Now we need to find a way to get rid of the mutable state. First of all we get rid of the "visitlist" variable by making dfs return that instead of void:

``````visited = set()  #mutable state
def dfs(node):
if isMember(node, visited):
return []
else:
visited[node.key] = true
return [node.key] + concat(map(dfs, node.children))
``````

And now comes the tricky part: getting rid of the "visited" variable. The basic trick is to use a convention where we pass the state as an additional parameter to functions that need it and have those functions return the new version of the state as an extra return value if they want to modify it.

``````let increment_state s = s+1 in
let extract_state s = (s, 0) in

let s0 = 0 in
let s1 = increment_state s0 in
let s2 = increment_state s1 in
let (x, s3) = extract_state s2 in
-- and so on...
``````

To apply this pattern to the dfs, we need to change it to receive the "visited" set as an extra parameter and to return the updated version of "visited" as an extra return value. Additionally, we need to rewrite the code so that we are always passing forward the "most recent" version of the "visited" array:

``````def dfs(node, visited1):
if isMember(node, visited1):
return ([], visited1) #return the old state because we dont want to  change it
else:
curr_visited = insert(node.key, visited1) #immutable update, with a new variable for the new value
childtrees = []
for child in node.children:
(ct, curr_visited) = dfs(child, curr_visited)
child_trees.append(ct)
return ([node.key] + concat(childTrees), curr_visited)
``````

The Haskell version does pretty much what I did here, except that it goes all the way and uses an inner recursive function instead of mutable "curr_visited" and "childtrees" variables.

As for monads, what they basically accomplish is implicitly passing the "curr_visited" around, instead of forcing you to do it by hand. Not only does this remove clutter from the code, but it also prevents you from making mistakes, such as forking state (passing the same "visited" set to two subsequent calls instead of chaining the state).

• I knew there had to be a way to make it less painful, and maybe more readable, because I'm having a hard time understanding your example. Should I go for monads or better practice more to understand code like yours? Oct 5, 2013 at 17:45
• @bigstones: I think you should try to understand how my code works before tackling monads - they will basically do the same thing I did but with extra layers of abstraction to confuse you. Anyway, I added some extra explanation to try to make things a bit clearer Oct 5, 2013 at 18:47
• "Functional programming doesn't get rid of state. It only makes it explicit!": This is really clarifying! Jan 11, 2014 at 17:31
• "[Monads] let you pass the state variable around implicitly and the interface guarantees that it happens in a single-threaded manner" <- This is an illuminative description of monads; outside the context of this question, I may replace 'state variable' with 'closure' Aug 8, 2017 at 6:00

Here's a simple answer relying on `mapConcat`.

`````` mapConcat :: (a -> [b]) -> [a] -> [b]
-- mapConcat is in the std libs, mapConcat = concat . map
type Path = []

isReachable :: a -> Auto a -> a -> [Path a]
isReachable to auto from | to == from = [[]]
isReachable to auto from | otherwise =
map (from:) . mapConcat (isReachable to auto) \$ neighbors auto from
``````

Where `neighbors` returns the states immediately connected to a state. This returns a series of paths.