Funktionelle Programmierung für 3 Listen in Racket

Question

Ich könnte folgenden Code verwalten, um Elemente in einer Liste mit 2 anderen Listen zu ersetzen. Orilist und newlist haben ursprüngliche und neue Begriffe in der Reihenfolge. Der Ersatz wird mit orilist getan und newlist- wenn orilist Artikel in slist sind, wird verändert slist neue Objekte aus newlist haben entsprechen:

(define (list-replace-from-lists slist orilist newlist) 
    (define replaced #f) 
    (define outl '()) 
    (for ((item slist)) 
    (set! replaced #f) 
    (for ((ori_ orilist) (i (in-naturals)) #:when (equal? item ori_)) 
     (set! outl (cons (list-ref newlist i) outl)) 
     (set! replaced #t)) 
    (when (not replaced) 
     (set! outl (cons item outl)))) 
    (reverse outl)) 

2 und 5 bis 12 und 15, die jeweils in (Liste zu ersetzen, 1 2 3 4 5 6):

(list-replace-from-lists (list 1 2 3 4 5 6) (list 2 5) (list 12 15)) 

Ausgang ist:

'(1 12 3 4 15 6) 

obigen Code jedoch nicht funktionsfähig sieht und hat viele Satz! Aussagen. Wie kann dies in funktionalen Code umgewandelt werden? Sollte ich Strukturen oder andere Datentypen für diesen Zweck verwenden?

Bearbeiten: Elemente können in der ursprünglichen Liste, z. (list 1 2 3 4 5 2 6)

Answer 1

Sie können weiterhin Listen verwenden und alles funktionsfähig halten. :-) Hier ist meine Lösung:

(define (replace-all haystack needles new-needles) 
    (define replace-alist (map cons needles new-needles)) 
    (define (replace-one item) 
    (cond ((assoc item replace-alist) => cdr) 
      (else item))) 
    (map replace-one haystack)) 

Erklärung des Codes:

1. Zuerst bauen wir einen Ersatz Assoziationsliste (alist). Dies ist eine Liste von Paaren, deren Schlüssel der needles entsprechen und die Werte entsprechen new-needles.

2. Dann definieren wir eine replace-one Funktion, die ein Element nimmt und sieht, ob es mit einem der Schlüssel in der Alist übereinstimmt. Wenn ja, geben wir den entsprechenden Wert zurück; Andernfalls geben wir den ursprünglichen Artikel zurück.

3. Schließlich ordnen wir die haystack durch replace-one zu. Yay Funktionen höherer Ordnung!

Beachten Sie, dass dieser Code O(m*n) ist, wo m ist die Größe der haystack und n ist die Größe der needles, die die gleiche Laufzeit wie Ihre Version. Wenn needles groß ist, sollten Sie eine Hashtabelle anstelle eines Alist verwenden, wodurch sich die Laufzeit der Funktion auf O(m) amortisiert.

Answer 2

Dies ist eine funktionale Lösung, die Hash verwendet, um die Verknüpfungen beizubehalten. Das macht diese Lösung O (Heuhaufenlänge Nadellänge), da unveränderliche Hashes mit Bäumen implementiert werden.

(define (list-replace-all haystack needles new-values) 
    ;; make a dictionary of elements to be replaced 
    (define hash 
    (foldl (λ (needle new-value hash) 
      (hash-set hash needle new-value)) 
      #hash() 
      needles 
      new-values)) 
    ;; do the replace. If not in hash the actual key is default 
    (map (λ (e) (hash-ref hash e e)) haystack)) 

(list-replace-all '(1 2 3 4 5 6) '(2 5) '(12 15)) 
; ==> (1 12 3 4 15 6)