Stack implementation in recursive function

Question

I'm trying to implement a recursive backtracking function using depth first search and I'm stuck in a point where I need to know my previous position in a matrix.

The idea is this: I have a matrix as a 2D Array and this is my function:

Mark the current point,if the point is what I'm looking for, I set the point in the matrix as part of the solution and all the previously marked points as part of the solution as well. Else I call the function to a valid adjacent point.

The problem is the third case: if there are no valid adjacents points, then I need to mark the point as wrong and call the function to my previous location. To do that I think I need a stack that keeps track of my previous movement but I'm having an hard time figuring out how to do so in f#.

let rec  solve (x,y) =

         mark (x,y)

         if (x,y) = pointimlookingfor then
           for x in 0.. array width-1 do
               for y in 0..array height-1 do
                   if Myarray.[x,y]=markedpoint then
                      Myarray.[x,y]<-partofsolution

         else if (List.isEmpty(adjacentslist) then
              Myarray.[x,y]<-wrong point
              solve (the previous visited point)

         else 
              for (adjacentpoint) in adjacentslist do
                   solve(adjacentpoint)

Any ideas?

Answer 1

In most functional languages, the default list type is an immutable linked-list, which you can use as a simple stack, because of its construction.

cons is push into stack, and head is pop from stack. With that, we can write a simple stack module.

module Stack =
    let empty = []
    let push item stack = item::stack
    let pop = function
    | [] -> failwith "No items in stack"
    | x::xs -> xs
    let peek stack = stack |> List.tryHead

So,

Stack.empty |> Stack.push 1 |> Stack.push 2 |> Stack.pop |> Stack.pop = Stack.empty //true

In actual practice, instead of explicitly using functions like the above, the easiest way is to use pattern matching on some accumulator which you carry with you as you recurse/fold.

For an example, let's re-create a classic use-case for a stack - balancing parenthesis. Every time you encounter an open brace, you push to stack, when you encounter a closing brace, you pop from the stack, and see if it matches the last one you pushed in. If it doesn't, it's unbalanced.

let rec isBalanced stack = function
| '(' | '{' | '[' as opened -> opened::stack //push into stack
| ')' | '}' | ']' as closed -> 
    match stack with
    | opened::rest as all -> //pop from stack
        match opened, closed with
        | '(', ')' 
        | '{', '}' 
        | '[', ']' -> rest
        | _ -> failwith "Mismatched braces"
    | [] -> failwith "Closing before open"
| _ -> stack

"abc() { [ 1; 2; 3] }" |> Seq.fold (isBalanced) [] 

There are more concise ways to write this, but this illustrates how you can simulate a classical stack with immutable structures.

In your case, you could push an (x,y) tuple on to the stack, and let the algorithm backtrack by destructuring it: (x,y)::tail.