라켓에서 3 개 목록에 대한 기능 프로그래밍

Question

다음 코드를 관리하여 다른 두 목록을 사용하여 목록의 항목을 대체 할 수있었습니다. Orilist와 newlist는 원래 용어와 새로운 용어를 순서대로 사용합니다.

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

은 (목록에서 각각 12, 15 (2)와 (5)를 대체하기 : 여분이 orilist 및 orilist 항목 SLIST 존재할 경우 newlist-, SLIST가 newlist에서 새로운 아이템을 대응하도록 변화를 사용하여 수행 1 2 3 4 5 6)

'(1 12 3 4 15 6) 

그러나, 상기 기능 코드 보이지 않는 많은 세트를 가지고

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

출력한다! 진술. 어떻게 이것을 기능 코드로 변환 할 수 있습니까? 위의 목적을 위해 구조물이나 다른 데이터 유형을 사용해야합니까?

수정 : 항목이 원본 목록에 재발행 될 수 있습니다. 예 : (list 1 2 3 4 5 2 6)

Answer 1

여전히 목록을 사용하고 모든 기능을 계속 사용할 수 있습니다. 코드의

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

설명 : :-) 여기 내 솔루션입니다

1. 첫째, 우리는 대체 연관리스트를 (alist)를 구축 할 수 있습니다. 이것은 키 쌍이 needles에 해당하고 값이 new-needles에 해당하는 쌍 목록입니다.

2. 그런 다음 항목을 취하는 함수를 정의하고 알리 스트의 키 중 하나와 일치하는지 확인합니다. 그렇다면 해당 값을 반환합니다. 그렇지 않으면 원래 항목을 반환합니다.

3. 마지막으로 haystack부터 replace-one까지를 매핑합니다. Yay higher-order functions! 이 코드는 m이 haystack 및 n의 크기 O(m*n) 것을

주 버전과 같은 런타임이다 needles의 크기입니다. needles이 큰 경우에는 alist 대신 해시 테이블을 사용하여 함수의 런타임을 O(m)으로 분할합니다.

Answer 2

이것은 해시를 사용하여 연결을 유지하는 기능적 솔루션입니다. 불변의 해시가 나무로 구현 되었기 때문에이 솔루션은 O (haystack-length 로그 바늘 길이)를 만듭니다.

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