Can branch and bound algorithms be implemented purely functionally?
algorithm, branch-and-bound, functional-programming
Solution
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`.
Problem
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?