¿Cómo implementar una bifurcación en un lenguaje de programación funcional?

Estoy tratando de escribir una búsqueda de bifurcación y enlace en el conjunto de todas las funciones f: D -> R, donde el tamaño del dominio es pequeño (| D | ~ 20) y el rango es mucho mayor (| R | ~ 2 ^ 20 ) Inicialmente, se me ocurrió la siguiente solución.

(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))))))))

Aquí, el parámetro condlistde la función builderes una lista de condiciones que una solución debe cumplir. La función checkdevuelve nil si el elemento viola algún elemento de la lista de condiciones partial-map. La función recur-on-firstasigna el primer elemento del dominio al primer elemento del rango e intenta construir una solución a partir de ahí. De lo contrario, se recur-on-firstinvoca para intentar construir una solución que asigne el primer elemento del dominio a otro elemento que no sea el primero en el rango. Sin embargo, debe mantener una lista ignoredque almacene estos elementos descartados (como el primer elemento del rango) ya que podrían ser imágenes de algunos otros elementos en el dominio.

Hay dos problemas que puedo ver con esta solución. La primera es que las listas ignoredy rangela función recur-on-firstson bastante grandes y appendsu uso es una operación costosa. El segundo problema es que la profundidad de recursión de la solución depende del tamaño del rango.

Entonces se me ocurrió la siguiente solución que utiliza listas doblemente vinculadas para almacenar los elementos en el rango. Las funciones start, nexty endproporcionan instalaciones para iterar sobre la lista doblemente enlazada.

(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))))))

El tiempo de ejecución de la segunda solución es mucho mejor que el tiempo de ejecución de la primera solución. La appendoperación en la primera solución se reemplaza por elementos de empalme dentro y fuera de una lista doblemente vinculada (estas operaciones son de tiempo constante) y la profundidad de recursión solo depende del tamaño del dominio. Pero mi problema con esta solución es que usa Ccódigo de estilo. Así que mi pregunta es esta.

¿Existe una solución que sea tan eficiente como la segunda solución pero que no use setfestructuras de datos mutables? En otras palabras, ¿existe una solución de programación funcional eficiente para este problema?

Primera idea que viene a la mente: use el mismo enfoque general, pero reemplace el bucle con una llamada recursiva de cola cuyo parámetro es la lista empalmada para la siguiente etapa del cálculo. Nunca tiene que modificar la lista empalmada, solo genere una nueva lista en cada etapa. Es cierto que no es un tiempo constante, pero de todos modos debe recorrer la lista para encontrar dónde empalmar. Incluso podría reutilizar la mayoría de los nodos, especialmente si puede usar una lista enlazada individualmente.