How to deal with 'losing objects' in functional programming? [closed]

Question

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?

Answer 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.)