I am trying to write a branch and bound search on the set of all functions f: D -> R, where the domain size is small (|D| ~ 20) and the range is much bigger (|R| ~ 2^20). Initially, I came up with the following solution.
(builder (domain range condlist partial-map) (let ((passed? (check condlist partial-map))) (cond ((not passed?) nil) (domain (recur-on-first domain range condlist partial-map '())) (t partial-map)))) (recur-on-first (domain range condlist partial-map ignored) (cond ((null range) nil) (t (let ((first-to-first (builder (cdr domain) (append ignored (cdr range)) condlist (cons (cons (car domain) (car range)) partial-map)))) (or first-to-first (recur-on-first domain (cdr range) condlist partial-map (cons (car range) ignored))))))))
Here the parameter
condlist to the function
builder is a list of conditions that should be satisfied by a solution. The function
check returns nil iff any element in the list of conditions is violated by the
partial-map. The function
recur-on-first assigns the first element in the domain to the first element in the range and tries to build a solution from there. Failing this
recur-on-first invokes itself to try and construct a solution that assigns the first element in the domain to some element other than the first one in the range. However, it has to maintain a list
ignored that stores these discarded elements (like the first element in the range) as they could be images of some other elements in the domain.
There are two problems that I can see with this solution. The first one is that the lists
range in the function
recur-on-first are quite large and
appending them is an expensive operation. The second problem is that the recursion depth of the solution depends on the size of the range.
So I came up with the following solution that uses doubly linked lists to store the elements in the range. The functions
end provide facilities to iterate over the doubly linked list.
(builder (domain range condlist &optional (partial-map nil)) (block builder (let ((passed? (check condlist partial-map))) (cond ((not passed?) nil) (domain (let* ((cur (start range)) (prev (dbl-node-prev cur))) (loop (if (not (end cur)) (progn (splice-out range cur) (let ((sol (builder (cdr domain) range condlist (cons (cons (car domain) (data cur)) partial-map)))) (splice-in range prev cur) (if sol (return-from builder sol))) (setq prev cur) (setq cur (next cur))) (return-from builder nil))))) (t partial-map))))))
The runtime of the second solution is much better than the runtime of the first solution. The
append operation in the first solution is replaced by splicing elements in and out of a doubly linked list (these operations are constant time) and the recursion depth only depends on the size of the domain. But my problem with this solution is that it uses
C style code. So my question is this.
Is there a solution that is as efficient as the second solution but does not use
setfs and mutable data structures? In other words, is there an efficient functional programming solution to this problem?