Sto provando a scrivere un ramo e la ricerca legata sul set di tutte le funzioni f: D - > R, dove la dimensione del dominio è piccola (| D | ~ 20) e l'intervallo è molto più grande (| R | ~ 2 ^ 20). Inizialmente, ho trovato la seguente soluzione.
(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))))))))
Qui il parametro condlist alla funzione builder è una lista di condizioni che dovrebbero essere soddisfatte da una soluzione. La funzione check restituisce nil se if qualsiasi elemento nell'elenco di condizioni viene violato da partial-map . La funzione recur-on-first assegna il primo elemento nel dominio al primo elemento dell'intervallo e tenta di creare una soluzione da lì. Se questo recur-on-first fallisce, tenta di creare una soluzione che assegni il primo elemento nel dominio a un elemento diverso dal primo dell'intervallo. Tuttavia, deve mantenere una lista ignored che memorizza questi elementi scartati (come il primo elemento dell'intervallo) in quanto potrebbero essere immagini di alcuni altri elementi nel dominio.
Ci sono due problemi che posso vedere con questa soluzione. Il primo è che gli elenchi ignored e range nella funzione recur-on-first sono piuttosto grandi e append li è un'operazione costosa. Il secondo problema è che la profondità di ricorsione della soluzione dipende dalla dimensione dell'intervallo.
Quindi ho trovato la seguente soluzione che utilizza elenchi doppiamente collegati per memorizzare gli elementi nell'intervallo. Le funzioni start , next e end forniscono funzionalità per scorrere l'elenco doppiamente collegato.
(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))))))
Il runtime della seconda soluzione è molto meglio del runtime della prima soluzione. L'operazione append nella prima soluzione viene sostituita da elementi di splicing in entrata e in uscita da una lista doppiamente collegata (queste operazioni sono a tempo costante) e la profondità di ricorsione dipende solo dalla dimensione del dominio. Ma il mio problema con questa soluzione è che usa il codice di stile C . Quindi la mia domanda è questa.
Esiste una soluzione efficiente come la seconda soluzione ma non utilizza setf s e strutture dati mutabili? In altre parole, esiste una soluzione di programmazione funzionale efficiente per questo problema?