Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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:

digraph representing an automaton

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)

share|improve this question
3  
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. –  Ptharien's Flame Oct 4 '13 at 23:08
1  
@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 :) –  bigstones Oct 4 '13 at 23:40
1  
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. –  Philipp Oct 4 '13 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. –  Ptharien's Flame Oct 5 '13 at 1:26
4  
@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. –  hugomg Oct 5 '13 at 15:21

2 Answers 2

up vote 12 down vote accepted

Functional programming doesn't get rid of state. It only makes it explicit! While its true that functions like map will often "unravel" a "shared" data structure, if all you want to do is write a reachability algorithm then its 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 (its easy to use s' instead of s'', its easy top 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 sate 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 acomplish 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).

share|improve this answer
    
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? –  bigstones Oct 5 '13 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 –  hugomg Oct 5 '13 at 18:47
1  
"Functional programming doesn't get rid of state. It only makes it explicit!": This is really clarifying! –  Giorgio Jan 11 at 17:31

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.