Can branch and bound algorithms be implemented purely functionally?

Question

General Description of Branch and Bound

From Wikipedia's Branch and Bound:

This step is called pruning, and is usually implemented by maintaining a global variable m (shared among all nodes of the tree) that records the minimum upper bound seen among all subregions examined so far. Any node whose lower bound is greater than m can be discarded.

Practical Example: Traveling Salesman Problem

A simple solution to the Traveling Salesman Problem is to keep a variable, e.g. best, that represents the shortest Hamiltonian Circuit found so far (upper bound).

Every time we consider a new step in a potential new circuit, we compute the cost of the path at the current point, e.g. cost, which is a lower bound on the cost of this path, and compare it to the best variable. If at any point cost >= best, we need not consider this path; we may prune all potential paths that begin with this subpath.

This is not difficult to implement in a procedural language such as C where we can create a variable that is in the scope of the function. For example,

int best = -1; // no best path yet

node* solveTSP() {
    // best can be consulted and has a consistent
    // value across all recursive calls to solveTSP()
    ...
}

My Actual Question

It is not clear to me how such an algorithm would be implemented purely functionally. Is there a way to simulate the global variable m mentioned in wikipedia's definition?

I know that it is simple to have a global variable in Lisp, but is this possible in a more purely-functional language such as Haskell?

Answer 1

You simply pass the current best value as an additional argument to recursive calls and also return the updated best value as the a part of their results. So if you have a function of type a -> b, it becomes something like a -> Int -> (b, Int). Instead of reading the global variable, you read the additional argument, and instead of writing it, you return a modified value when the function finishes.

This can be nicely expressed using the state monad. Type Int -> (b, Int) is isomorphic to State Int b, so our function of type a -> b becomes a -> State Int b.

Answer 2

Computation with mutable state is no more powerful than computation without it. One can be reduced to the other.

In particular, a mutable cell in a functional viewpoint becomes a sequence of successive values, usually in some arrangement where new copies shadow older ones (for example, in tail recursion.)