3

I am working with Haskell, and one of the big problems I have with writing programs is that when I want to do something to an object, my program forgets everything I did with it before. When you implement trees with zippers for example, to be able to tell where you are on the tree, every time you move you have to store all the nodes to your left and right in your path. Similarly, if I want to write a simple depth first search, I feel like I have to keep another, separate record of which vertices I've visited, and which I want to go to next, lest I return to an old vertex and forget where I've been.

My question is: does this keep happening? Is the 'correct' way to write functional programs for data that changes to drag around all the things you've done in the past?

preferred_anon
  • 538
  • 4
  • 11
  • 1
    it's hard to tell in this generality (what are data that change?) - for example an usual approach to write algorithms dealing with trees is to write recursive functions (as trees are normally defined recursive themselves) - here you don't have to remember the *path* as the recursion will do it for you - but yes if you want to move inside such structures and want to edit them locally zippers are a good idea – Random Dev Aug 17 '15 at 20:42
  • 2
    Having to remember which nodes have already been visited is part of dfs (and any other search). You can bake that information into your graph of course, but what that primarily buys you is making your graph structure more complex for an often negligible gain in performance. – Cubic Aug 17 '15 at 22:15
  • 1
    For graphs specifically, checkout inductive graphs and the [fgl](https://hackage.haskell.org/package/fgl). I recently wrote an answer about [breadth first search](http://stackoverflow.com/questions/30464163/functional-breadth-first-search/30469287#30469287) which fits just as well for depth-first search. For more detail, check out my blog post about [generating mazes with inductive graphs](http://jelv.is/blog/Generating-Mazes-with-Inductive-Graphs). – Tikhon Jelvis Aug 17 '15 at 23:25

1 Answers1

1
data SimpleTree a = Leaf a | Branch a (SimpleTree a) (SimpleTree a)

dfs :: Eq a => a -> SimpleTree a -> Bool
dfs val (Leaf v2) = v2 == val
dfs val (Branch v2 t2 t3) = v2 == val
                            || dfs val t2
                            || dfs val t3

Then:

*Main> let sampleTree = Branch 5 (Branch 4 (Leaf 3) (Leaf 2)) (Leaf 6)
*Main> map (\n -> dfs n sampleTree) [1..7]
[False,True,True,True,True,True,False]

My DFS algorithm does not explicitly carry around a list of visited tree nodes.

The correct way to write algorithms for your structures depends on your structures, but there is no universal requirement that you drag around a list of visited nodes. (Zippers do have that requirement - it's essential to how they work.)

WolfeFan
  • 1,447
  • 7
  • 9
  • Your "dfs" only works because your graph is a directed tree. There is no way to traverse a directed tree that involves revisiting previous nodes that isn't completely idiotic. For non-acyclic graphs you have to remember previously visited nodes _somehow_. – Cubic Aug 17 '15 at 22:08
  • I interpreted the question as "Do you always need to store visited nodes for all data structures in Haskell" and demonstrated that the answer is "no". For non-acyclic graphs, you do need to track visited nodes, regardless of language choice, but that's assuming a different set of specifics than the question referred to. – WolfeFan Aug 17 '15 at 22:21
  • 1
    The OP seems to be implicitly talking about graph DFS. They also seem to be imagining that this need to track paths is arising out of the limitations of functional programming, rather than being to do with the particular problem they're working on (and that you wouldn't need to track visited nods in a graph DFS implementation in a non-functional language). – Ben Aug 17 '15 at 22:43